What natures and EV spreads are you using for each of your Pokemon? Those are important too, you know.
Arcanine has good coverage, yes, but it tends to be overshadowed by Talonflame and Heatran, as the former has priority Brave Bird (thanks to Gale Wings) for revenge killing weakened targets, while the latter is rather versatile. Even Infernape is better, as it's not weak to Stealth Rock, is faster (though it's not too fast), and can even go mixed to better handle walls:
Heatran:
-Stealth Rock
-Lava Plume
-Toxic
-Taunt/Protect/Roar
Nature: Calm
EVs: 248 HP/192 SDef/68 Spe
Item: Leftovers
or
-Magma Storm
-Earth Power
-Taunt
-Toxic/Solar Beam
Nature: Timid
EVs: 252 SAtk/4 SDef/252 Spe
Item: Leftovers/Air Balloon/Power Herb
or
-Fire Blast
-Flash Cannon/Stone Edge/Hidden Power (Ice)
-Earth Power
-Stealth Rock
Nature: Timid
EVs: 252 SAtk/4 SDef/252 Spe
Item: Air Balloon
or
-Overheat/Fire Blast
-Flash Cannon
-Earth Power/Hidden Power (Ice)
-Stone Edge/Ancient Power
Nature: Timid
EVs: 28 HP/252 SAtk/228 Spe
Item: Choice Scarf
Infernape:
-Fire Blast/Flare Blitz
-Close Combat
-Gunk Shot
-Grass Knot/Mach Punch/Hidden Power (Ice)
Nature: Naive
EVs: 100 Atk/156 SAtk/252 Spe
Item: Life Orb
Talonflame:
-Swords Dance
-Flare Blitz
-Brave Bird/Acrobatics
-Roost
Nature: Jolly
EVs: 252 Atk/4 Def/252 Spe
Item: Sharp Beak/Sky Plate/none
Ability: Gale Wings
or
-Swords Dance
-Brave Bird/Acrobatics
-Taunt/Will-o-Wisp
-Roost
Nature: Adamant
EVs: 248 HP/252 Atk/8 Spe
Item: Leftovers/none
Ability: Gale Wings
or
-Flare Blitz
-Brave Bird
-U-turn
-Steel Wing/Tailwind
Nature: Adamant
EVs: 252 Atk/4 Def/252 Spe
Item: Choice Band
Ability: Gale Wings
or
-Brave Bird/Acrobatics
-Bulk Up/Will-o-Wisp
-Taunt/Will-o-Wisp
-Roost
Nature: Careful
EVs: 248 HP/252 SDef/8 Spe
Item: Leftovers/none
Ability: Gale Wings
Take note that you can only Mega Evolve one Pokemon per battle, so having Mega Gyarados and Mega Venusaur on the same team is pointless. Ferrothorn is a better defensive alternative:
-Stealth Rock
-Leech Seed
-Power Whip/Protect
-Gyro Ball/Thunder Wave
Nature: Relaxed
EVs: 252 HP/88 Def/168 SDef
Item: Leftovers/Shed Shell/Rocky Helmet
Ability: Iron Barbs
Froslass is fast, sure, but its offensive presence is lacking; Gengar is just as fast and is stronger. Garchomp outclasses Flygon in every way possible, as the former is stronger and faster.
Garchomp:
-Stealth Rock
-Outrage/Dragon Claw
-Earthquake
-Fire Blast/Swords Dance
Nature: Naive/Jolly
EVs: 252 Atk/4 SAtk/252 Spe
Item: Lum Berry/Focus Sash/Rocky Helmet
or
-Swords Dance
-Outrage/Dragon Claw
-Earthquake
-Stone Edge/Substitute
Nature: Jolly
EVs: 4 HP/252 Atk/252 Spe
Item: Lum Berry/Leftovers/Salac Berry
or
-Stealth Rock
-Dragon Tail
-Earthquake/Toxic
-Fire Blast/Toxic
Nature: Impish
EVs: 240 HP/176 Def/92 Spe
Item: Rocky Helmet
Ability: Rough Skin
or
-Outrage
-Earthquake
-Stone Edge/Fire Blast
-Dragon Claw/Fire Blast
Nature: Jolly/Naive
EVs: 4 HP/252 Atk/252 Spe
Item: Choice Scarf
or
-Draco Meteor
-Earthquake
-Stone Edge/Stealth Rock
-Fire Blast
Nature: Naive
EVs: 4 Atk/252 SAtk/252 Spe
Item: Life Orb
Gengar:
-Shadow Ball
-Sludge Wave/Sludge Bomb
-Focus Blast
-Taunt/Icy Wind/Destiny Bond/Substitute
Nature: Timid
EVs: 4 Def/252 SAtk/252 Spe
Item: Life Orb/Focus Sash/Black Sludge
or
-Hex
-Taunt
-Will-o-Wisp
-Sludge Wave/Sludge Bomb/Substitute
Nature: Timid
EVs: 8 HP/248 SAtk/252 Spe
Item: Black Sludge
You need hazard clearers (Rapid Spin and Defog) on the team, as Talonflame and pre-Mega Gyarados weak to Stealth Rock. Examples are Mandibuzz and Starmie:
Mandibuzz:
-Foul Play
-Taunt/Toxic
-Defog/Toxic/Knock Off
-Roost
Nature: Bold/Impish
EVs: 248 HP/136 Def/108 SDef/16 Spe
Item: Leftovers
Ability: Overcoat
Starmie:
-Scald
-Psyshock/Reflect Type
-Rapid Spin
-Recover
Nature: Timid
EVs: 252 HP/4 Def/252 Spe
Item: Leftovers
Ability: Natural Cure
or
-Hydro Pump
-Psyshock/Thunderbolt
-Ice Beam/Hidden Power (Fire)
-Rapid Spin/Recover
Nature: Timid
EVs: 4 Def/252 SAtk/252 Spe
Item: Life Orb
Ability: Natural Cure/Analytic
