Mega Gyarados is one of the more interesting Mega Pokemon out there, IMO. It can hold off Mega Evolution until the right moment by using its regular form to take out counters to its Mega form:
-Dragon Dance
-Waterfall
-Earthquake
-Bite/Stone Edge/Substitute
Nature: Adamant
EVs: 32 HP/252 Atk/224 Spe
Item: Gyaradosite
Ability: Intimidate
Since regular Gyarados is weak to Stealth Rock, Rapid Spin or Defog support is appreciated:
Starmie:
-Hydro Pump/Surf
-Thunderbolt/Psyshock
-Ice Beam
-Rapid Spin
Nature: Timid
EVs: 252 SAtk/4 SDef/252 Spe
Item: Leftovers/Life Orb
Ability: Natural Cure
or
-Scald
-Rapid Spin
-Psyshock/Ice Beam/Thunderbolt
-Recover
Nature: Timid
EVs: 248 HP/32 Def/4 SAtk/224 Spe
Item: Leftovers
Ability: Natural Cure
Excadrill:
-Earthquake
-Rock Slide/Iron Head
-Rapid Spin
-Swords Dance/Stealth Rock
Nature: Jolly
EVs: 4 HP/252 Atk/252 Spe
Item: Life Orb/Air Balloon/Chople Berry
Ability: Mold Breaker
or
-Swords Dance
-Earthquake
-Rapid Spin
-Rock Slide/Substitute/Iron Head
Nature: Adamant
EVs: 176 HP/60 Atk/252 SDef/20 Spe
Item: Leftovers
Ability: Mold Breaker
Mandibuzz:
-Foul Play
-Roost
-Taunt/Whirlwind
-Defog/Toxic/Knock Off
Nature: Bold/Impish
EVs: 248 HP/216 Def/44 SDef
Item: Leftovers
Ability: Overcoat
Crobat:
-Brave Bird
-Defog
-Roost
-Taunt/Toxic
Nature: Jolly
EVs: 168 HP/136 Atk/4 SDef/200 Spe
Item: Black Sludge
Ability: Infiltrator
Tentacruel:
-Scald
-Sludge Bomb
-Rapid Spin
-Toxic/Knock Off
Nature: Bold
EVs: 252 HP/224 Def/32 Spe
Item: Black Sludge
Ability: Liquid Ooze
Other teammates to include are Talonflame, to eliminate Grass Pokemon, and Scizor to bring in Gyarados with a slow U-turn:
Talonflame:
-Swords Dance
-Flare Blitz
-Brave Bird
-Roost
Nature: Adamant
EVs: 252 Atk/4 Def/252 Spe
Item: Life Orb/Sharp Beak/Sky Plate
Ability: Gale Wings
or
-Flare Blitz
-Brave Bird
-U-turn
-Will-o-Wisp/Tailwind
Nature: Adamant
EVs: 252 Atk/4 Def/252 Spe
Item: Choice Band
Ability: Gale Wings
or
-Bulk Up
-Brave Bird
-Roost
-Taunt/Substitute
Nature: Careful
EVs: 248 HP/184 SDef/76 Spe
Item: Leftovers
Ability: Gale Wings
Scizor:
-U-turn
-Bullet Punch
-Superpower/Brick Break
-Pursuit/Knock Off
Nature: Adamant
EVs: 248 HP/252 Atk/8 SDef
Item: Choice Band
Ability: Technician
or
-Swords Dance
-Bullet Punch
-Bug Bite/X-Scissor/U-turn
-Roost
Nature: Adamant
EVs: 248 HP/40 Atk/220 SDef
Item: Leftovers
Ability: Technician