Flying types prior to Eterna Gym:
Staraptor (much grind)
Crobat (much grind)
Butterfree (evolve from Caterpie, requires dual-slot with FireRed version)
Drifblim (much grind)
Chatot (in-game trade)
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.