I've been extremely successful with Mega Gyarados running a mono attacking resttalk DD set, but lately I've been running a mixed all out attacking DD Gyarados that seems to have pushed this guy to his full potential.
DD Mix Mega Gyarados
Gyarados @ Gyaradosite
Ability: Intimidate (Mold Breaker)
IVs: 252 Atk / 252 Spe / 4 Hp
Nature: Naughty/Naive
- Dragon Dance
- Waterfall
- Fire Blast
- Earthquake/Outrage/Substitute/Taunt
This Gyarados serves as a terrifying wallbreaker with enough bulk to take a few hits and obliterate unprepared teams. Base 155 Attack is nothing to be laughed at, and the fact that Mega Gyarados has uber-worthy bulk and the ability to get off an Intimidate means that it can force switches and snag and opportunity to set up right off the bat.
After +1, Mega Gyarados has the ability to dent the entire metagame with Waterfall/Outrage besides anything named Ferrothorn or Skarmory.
However, one commonly overlooked aspect of Gyarados's changes as it goes Mega is a +10 increase to his base Special Attack, going from a meager base 60 to a somewhat usable base 70. However, this slight increase gives it much needed power, as it now receives the opportunity to 2HKO it's biggest walls, Ferrothorn and Skarmory. Use it as a late game cleaner or a wallbreaker for other threats, but either way, Mega Gyarados has no hard counters this generation.
The last moveslot truly comes down to preference, as both Earthquake and Outrage have their own perks. Earthquake hits Azumarill, who would threaten Gyarados with a STAB Choice Banded Play Rough, while Outrage provides coverage against Flying type/levitating dragons, such as Lati@s and Dragonite. Note however that Gyarados can set up on Azumarill as long as it is locked into Waterfall, Superpower, or Aqua Jet, as a STAB Choice Banded Play Rough does a huge amount of damage even at -1. Substitute/Taunt allow Gyarados to set up on certain walls and avoid status, but this set is designed for wallbreaking and denting teams as quickly as possible.
As for natures, Naughty is preferable as it gives Gyarados a considerable buff in power, meaning that it can retain its wallbreaking capacity without even having to set up. Naive has very little use outside of allowing Gyarados to outspeed base 130s, +1 Jolly Dragonite, and +1 Timid Heatran. Naughty/Naive are prefered, as they preserve Gyarados's Special Attack while allowing it to set up on physical attackers after Intimidate.
As for teammates, this Gyarados needs something that can deal with whatever its last move doesn't cover. If Earthquake is used, a strong Fairy type should be used to cover for Gyarados's lack of coverage against Dragons. Choice Banded Azumarill is a great choice, as Gyarados breaks through what Azumarill can't muscle through while Azumarill packs a Dragon immunity and still applies immense offensive pressure. Ironically, if running Outrage, Azumarill becomes this set's number 1 enemy, so a strong Azumarill check is needed. Amoonguss checks Azumarill almost flawlessly this generation, as it boasts resistances to both of Azumarill's STAB attacks, Superpower, and Regenerator, meaning that it can take repeated onslaughts from Azumarill. A defog user such as Latias is appreciated as well; entry hazards have a greater negative impact on Gyarados than its opponents, as it will be OHKO/2HKOing them regardless. Latias is also a great check to Rotom-W, who threatens both regular and mega Gyarados with Volt Switch and Thunderbolt. Gyarados's job is more to clear a path for another physical sweeper than anything; Gyarados and Azumarill's excellent synergy cannot be stressed enough. They overcome each others' walls, becoming a dangerous pair of attackers.
Edit: I think I got a bit carried away with the analysis. I've been lurking for far too long :]