I agree that Gyarados holding Mega Stone is one of the most viable mons (maybe just "the most" suits it better right now). But I haven't convinced myself on neither the side of ban nor no-ban.
Up to now, there are many good points describing how powerful this mon is, and how much extra work each team-builder put in to prepare for it. Indeed, the complaint about it is a complicated combination of different characteristics, the typing, the ability, the sets and move-pools.
So here, I would like to make a small list of pokemons that can beat it in almost all circumstances. (It has to be incomplete, but I'm trying) These are, in my view, commonly viable mons in the meta. And maybe the fact that this list being short can be used as an argument of pro-ban, I would like to keep neutral about this issue for now as the standard of a balanced 1v1 metagame is something I still needs to think about. Indeed, many sets today are EVed to beat Gyarados-Mega specifically, but that is how 1V1 works since gen 6, so I am still hesitating about whether Gyarados is pushed over the edge in gen 7.
The following calc is taking into account of the most moves MGyarados brings: DD, Waterfall, Outrage, Taunt, Crunch, and EQ when tanking its hit; Considering the highest defense investment that is common enough: 252HP in bulk, or ~100HP ~100 Def combined, so we are calculating it as 252HP, 100 Def, which is over preparing in some way.
1. Tapu Koko 100% win
Either Z-Thunder or Z-Wild Charge set of Koko OHKO Gyarados-mega for whatever spread Gyarados is running.
2. Porygon-Z
Spec 90%
252 SpA Choice Specs Adaptability Porygon-Z Hyper Beam vs. 252 HP / 0 SpD Gyarados-Mega: 402-474 (102 - 120.3%) -- guaranteed OHKO
The Timid Spec Porygon-Z outspeeds all kinds of Gyarados and OHKO it unless heavily SpD invested, which is really uncommon. Considering the possible miss, take it as a 90% win.
The bulky scarf set of Elo Bandit usually works, but it depends on a not very favorable roll if the opposing Gyarados has a relatively high HP invest, plus possible flinch from waterfall.
252+ SpA Adaptability Porygon-Z Uproar vs. 252 HP / 0 SpD Gyarados-Mega: 178-210 (45.1 - 53.2%) -- 31.3% chance to 2HKO
3. Genesect
Spec 80%
While being able to 2HKO the most bulky set of Gyarados-mega, it can also survive a +1 STAB with some prepared investment. The win rate is around 80% considering the possible flinch.
200+ SpA Choice Specs Genesect Thunderbolt vs. 252 HP / 0 SpD Gyarados-Mega: 236-278 (59.8 - 70.5%) -- guaranteed 2HKO
+1 252+ Atk Mold Breaker Gyarados-Mega Waterfall vs. 196 HP / 0 Def Genesect: 256-303 (77.1 - 91.2%) -- guaranteed 2HKO
4. Magearna
With Choice spec, it has a decent chance of OHKO most of the gyarados sets.
252+ SpA Choice Specs Magearna Fleur Cannon vs. 252 HP / 0 SpD Gyarados: 349-412 (88.5 - 104.5%) -- 31.3% chance to OHKO
252+ SpA Choice Specs Magearna Fleur Cannon vs. 100 HP / 0 SpD Gyarados: 349-412 (98 - 115.7%) -- 87.5% chance to OHKO
It can also tolerates a flinch from waterfall if Gyarados does not bring EQ.
252 Atk Mold Breaker Gyarados-Mega Waterfall vs. 232 HP / 0 Def Magearna: 133-157 (37 - 43.7%) -- guaranteed 3HKO
The win rate depends on the spread, and possible thunderbolt mind game win.
5. Air Balloon Magnezone 76%
Air Balloon Magnezone uses Electroweb on turn 1 can win all variants of Mega Gyarados except when getting flinched from waterfall and then EQ to death, or electroweb misses. This is around 76% win rate.
It survives a +1 STAB, and Electroweb+Thunderbolt KOs the most viable bulky set.
252+ SpA Magnezone Thunderbolt vs. 252 HP / 0 SpD Gyarados-Mega: 258-306 (65.4 - 77.6%) -- guaranteed 2HKO
252+ SpA Magnezone Electroweb vs. 252 HP / 0 SpD Gyarados-Mega: 158-188 (40.1 - 47.7%) -- guaranteed 3HKO
6. Water-Fairy Type: Primarina and Tapu Fini resists both stab of Mgyara and are immune to outrage. While EQ will take more turns to take these mons down, Fairy Stab almost always KO Gyarados first.
+1 252 Atk Gyarados Earthquake vs. 252 HP / 64 Def Tapu Fini in Misty Terrain: 133-157 (38.6 - 45.6%) -- guaranteed 3HKO
192+ SpA Tapu Fini Moonblast vs. 252 HP / 0 SpD Gyarados: 130-154 (32.9 - 39%) -- 99.8% chance to 3HKO
+1 252 Atk Mold Breaker Gyarados-Mega Earthquake vs. 252 HP / 64 Def Tapu Fini: 156-184 (45.3 - 53.4%) -- 36.3% chance to 2HKO
45.6% + 53.4% < 100% while with Nature Madness+ Moonblast 3HKO whatever the play is, and 2HKO if Gyarados Mega Evolve right after DD.
252+ SpA Choice Specs Primarina Moonblast vs. 252 HP / 0 SpD Gyarados: 250-295 (63.4 - 74.8%) -- guaranteed 2HKO
+1 252 Atk Gyarados Earthquake vs. 252 HP / 0 Def Primarina: 204-240 (56 - 65.9%) -- guaranteed 2HKO
7. Pinsir-Mega 72%
+1 252 Atk Aerilate Pinsir-Mega Giga Impact vs. 252 HP / 100 Def Gyarados-Mega: 424-501 (107.6 - 127.1%) -- guaranteed OHKO
While outspeeding the fastest Gyarados-Mega, OHKO after a sword dance (even it is not hyper cutter) and being able to tank a hit of STAB from max attack Gyarados-Mega. Considering the 10% miss and possible flinch of waterfall, this is also around a 72% win rate.
+1 252+ Atk Mold Breaker Gyarados-Mega Waterfall vs. 0 HP / 4 Def Pinsir-Mega: 210-247 (77.4 - 91.1%) -- guaranteed 2HKO
8. Specificically prepared Metagross-Mega
200HP, 76+Def, 106 Atk, 128 Speed (to outspeed maxspeed Gyarados)
Before mega evolution, Metagross is immune to Intimidate. With sufficient bulk invest to Tank a +1 Crunch, and being able to 2HKO with Thunder Punch almost all the time.
+1 252+ Atk Mold Breaker Gyarados-Mega Crunch vs. 200 HP / 76+ Def Metagross-Mega: 296-350 (84.3 - 99.7%) -- guaranteed 2HKO
106 Atk Tough Claws Metagross-Mega Thunder Punch vs. 252 HP / 4 Def Gyarados-Mega: 194-230 (49.2 - 58.3%) -- 98.4% chance to 2HKO
8. Physically Bulky Grass Type has a high win rate in general, but may lose to double flinches.
Venusaur-Mega, Ferrothorn (possibly lose to Taunt + EQ if no Power Whip), Kartana, Tapu Bulu, Whimsicott with Giga Drain/Moonblast.
9. Z-reflect
While Fast and Fragile Specs Tapu Lele goes into 50/50 of picking thunderbolt or Moonblast turn 1 (if picked wrong it cannot OHKO and can be possibly OHKO back)
+1 252 Atk Mold Breaker Gyarados-Mega Crunch vs. 0 HP / 0 Def Tapu Lele: 283-334 (100.7 - 118.8%) -- guaranteed OHKO
The bulky Z-reflect varient, however, unless double flinched, would beat Gyarados-Mega.
252+ SpA Tapu Lele Moonblast vs. 252 HP / 0 SpD Gyarados-Mega: 272-324 (69 - 82.2%) -- guaranteed 2HKO
+1 252 Atk Mold Breaker Gyarados-Mega Waterfall vs. +1 200 HP / 56 Def Tapu Lele through Reflect: 88-104 (26.5 - 31.4%) -- guaranteed 4HKO
-----
Common but not guaranteed counters:
10. Bulky Zard-X when facing Gyarados really depends on the spread, the movepool, AND the play: whether the bulky Zard-X outspeeds and avoid getting Taunted, whether Mgyara has EQ, and the consequent set-up mind games.
facing 248HP 248 Def+ Zard-X but Gyara wins with EQ
http://replay.pokemonshowdown.com/gen71v1-530584625
Facing 248 HP 100+ Def Zard-X but Gyara wins with EQ
http://replay.pokemonshowdown.com/gen71v1-530585907
11. Chansey
Counter Chansey wins more than usual, while no-counter set fearing Taunt, 4HKO Gyarados with Seiss Toss while possibly 3HKOed by Waterfall.
Z-charm Umbreon can be beaten in an "waterfall then Taunt then waterfall twice" fashion. Flinch is not necessary if Umbreon is the common Bold 68 Def 248 HP spread, and even there is more investment in defense, there is a great possibility of getting one flinch.
http://replay.pokemonshowdown.com/gen71v1-530568912
Z-Charm Blissey goes into a mind game after turn 1 waterfall & Z-charmed. Taunt vs Soft Boil...If straight out using Seiss Toss and Waterfall, M Gyarados has a chance to win, but Blissey dose have a certain advantage in this mindgame, and Counter Blissey set usually wins.