Flying types, huh?
My favourite type!
I love birds.
I'd recommend taking the trouble to choose secondary typings and movesets to counter the weaknesses of bird Pokemon: electricity, ice, and rocks.
Teach your Gyarados Earthquake, and maybe include Gliscor (with Stone Edge and maybe Steel Wing) and Skarmory (with Mud-Slap, Fly and other annoying moves) because their secondary types counter two of the Flying type's three weaknesses.
You also might want to include Pokemon that can Levitate rather than fly, like Latias - it would be a bad move to make every Pokemon in your team a Flying-type, because you'd be vulnerable to sweepers such as Starmie that can learn a variety of moves for taking down birds. Also be sure to use various different types of attacks - both Physical and Special - to be sure you can take down not only the types you're weakest to, but also other types that can use those moves.
I've never battled in competition before, otherwise I would readily recommend Legendary Flying-types with massive stats and great movepools - but they're probably banned from the battles you have in mind...