I tested the CB set and it was decent. Here is how i suggest you make the set:
Gyarados @ Choice Band
Trait: Intimidate
EVs: 88 HP / 252 Atk / 168 Spe
Adamant Nature
- Waterfall / Aqua Tail
- Double-Edge
- Ice Fang / Stone Edge
- Earthquake
Other than Waterfall, Double Edge was the move i was using most of the time to catch on the swtch things such as Rotom-W, Scarf Keldeo (that may carry HP Electric), Politoed, Tentacruel, and even the occasional Lati@s. Great neutral coverage and hits hard most of the stuff that switch into Gyarados usually. Then Ice Fang follows up as the next most useful move to revenge kill Dragon-types, and hit Grass-types on the switch hard. Ice Fang also allows Gyarados to always OHKO 4 HP Breloom, acting as a nice check to it, after Sleep Clause has been activated. Stone Edge still lets you revenge kills dragon-types (with worse accuracy though), but also wrecks Kyurem-B and opposing Gyarados switch-ins, which is nice. It also lets you OHKO Volcarona under Sun. Finally EQ is an ok option for Jirachi, Jellicent, Tentacruel, Toxicroak, and Ninetales. Btw physically defensive Jellicent just barely avoids the 2HKO from CB EQ with SR in play (40.44 - 47.64%) and SpD Jelli is always 2HKOed. The EVs allow Gyarados to outpseed max Speed Adamant Breloom and the rest are put to HP. I think that this spread is very good, but if anyone has a better idea i am all ears...
Avalanche is good enough to be in AC, even though its negative priority sucks. Bite can go to AC too i guess, as it can 2HKO Jellicent and Celebi, as well as hit Starmie and Lati@s for very good damage (i know other moves already hit those Pokemon as well, but the point is that Bite hits them all together, sometimes lessening the need for prediction). As for good teammates, LO Starmie and bulky SubPunch Breloom were the best ones i used. SubPunch Breloom can switch into Jellicent with impunity, as well as Gastrodon, defensive Politoed, Rotom-W, and Tentacruel, and then do his stuff. LO Starmie spins for Gyara and provides immense wallbreaking power, leaving almost nothing to stand up to the two water-types (nothing in OU can wall their combo, although Celebi is a bit problematic as the only moves that can 2HKO Celebi are Gyarados's Double Edge and Ice Fang.
Bounce and Outrage are OO material for the Band set and for good reasons. Outrage on every non-Dragon type is a joke, and Gyarados is no exception. Why use Outrage just to hit a Jellicent you are not going to 2HKO anyway (it will just switch out), while you are stuck on a shitty move and many Pokemon can take advantage of you? Similarly Bounce on a choiced mon is a huge risk, because as long as the opponents bulky Steel / Electric / Tyranitar is alive, you ain't gonna do shit with it.