Flying types prior to Eterna Gym:
Gyarados (much grind)
Staraptor (much grind)
Crobat (much grind)
Butterfree (evolve from Caterpie, requires dual-slot with FireRed version)
Drifblim (much grind)
Chatot (in-game trade)
Combee (Honey Tree)
Vespiquen (much grind as it will be difficult to get a female Combee)
Mothim (evolve a male Burmy from a Honey Tree)
Personally I recommend Golbat, or Crobat if you can max its happiness super fast.
You can get Starly, Zubat, Hoothoot, Beautifly, Drifloon and Gligar.
Beautifly is a 1% encounter, so catching a Wurmple would be easier than hunting for it, and Drifloon can only be found once every Friday.
Source: Searching on Bulbapedia.