On the flip-side: Dodrio is a real glass cannon. If it doesn't KO, it most likely dies to the counter-attack. .__. It's a cool pokémon, though, and definitely worth consideration ingame because it's easy to raise and because STAB Drill Peck and Return are brutal, but it has serious trouble with standard physical wallers (even moreso than its sweeping comrades), which sort of limits its usefulness. It beats Swellow any day, though, (85 Atk with a lackluster movepool is not tremendous, peoples.) because the ingame AI is way too random for you to predict status accurately and the only thing that really gives Swellow a leg up on its competition (other than Endeavor) is its ability to absorb status. Dodrio has it beat in both movepool and statline because it doesn't matter how fast you are if you don't have the strength to KO what you hit.
Anyways, Mence is good, but if you already have a number of ice weaks on the team then it's just begging for Starmie & co to come and sweep you. (Important note, kiddies: never EVER run a team with a boltbeam weak. They get trampled. T_T) Another awesome flying type which I'm shocked that none of you have mentioned is Aerodactyl. It's fairly sturdy so it can switch into stuff, crazily fast and in possession of a good physical movepool and decent Atk. (Choice Band is highly recommended, though) It also has one considerable edge over most of its fellow fliers: the ability to learn Earthquake, which allows it to laugh at most electric types.
If you're looking for something within Emerald then I'd say Mence or - if you're looking for something with a bit more defensive flair - Skarmory. CB Ninjask is also fun, but you'd really need to breed in Silver Wind and it takes a bit of practice to play it well. (though it does give you one of the coolest pokémon in the game as a freebie when it evolves from Nincada <3) Crobat should not be neglected either; it's another pokémon that's fairly easy to raise, attainable early in the game and capable of putting quite a bit of hurt on the opponent, though unfortunately it does share a bit of Dodrio's drawbacks too. D=
Mind you, I certainly hope that you aren't planning on saddling the poor thing with Fly, because that's a sure-fire way of making any given pokémon suck. T_T For those needs, just take a Tropius and pack it with three other HM moves while you're at it (It can learn all except Surf and Waterfall). Whenever you use fly, you get to a pokémon center where you can switch a fighting pokémon back into the team anyway.
And of course Gyarados is also a very formidable flying type. :3