You people can advocate Moxmence all you want but Gyarados can single handedly annihilate teams with just 1 Dragon Dance, although 2 is preferred. While Gyarados is weak to electric, Breloom and Latios should be able to help with taking electric moves, and Gyarados is not weak to Ice, something that your team appears to have trouble with. Gyarados can take Fire moves for Breloom, Fighting moves aimed at Cloyster, and Ground and Water moves directed at Heatran.
Gyrados @ Leftovers/Water Gem
Trait: Moxie
EVs: 252 Atk / 4 Def / 252 Spd
Jolly Nature (+Spd, -SAtk)
- Dragon Dance
- Waterfall
- Ice Fang
- Earthquake
Leftovers is perfectly viable but having Gyarados hold a Water Gem gives your first use of Waterfall a 50% boost, helping to get the intial KO needed to set the ball rolling for Moxie, allowing you to use the resulting attack boost to further your sweep and so on. Dragon Dance is essential for raising your Speed to adequate levels, and while 1 Dragon Dance is usually enough, if you are given the chance to set up another, take it. Waterfall is STAB and at +1 with a Water Gem boost you've got a high chance of going to +2, if you know what I mean. Ice Fang hits Dragon types and Earthquake covers steel types. Gyarados is not a sweeper to be underestimated, as it can relentlessly pulverize unprepared teams (And some that are), with relative ease. Just make sure you get at least 1 Dragon Dance up or you will usually be revenged.