I'll answer because I think I can go more in-depth. Please tell me if I should hide this @GmaxWaluigi.
The fully evolved Pokemon in Black 2 that can learn Fly are: Crobat, Swoobat, Braviary, Mandibuzz, Sigilyph, Flygon, Archeops, Swanna, Volcarona, Tornadus, Thundurus, Landorus, Skarmory, Drifblim, Pelipper, Altaria, Delibird, Golurk, Hydreigon, Tropius, Reshiram, Zekrom, Kyurem, and Genesect.
You'll probably want it to have STAB, so this leaves us with: Crobat, Swoobat, Braviary, Mandibuzz, Sigilyph, Archeops, Swanna, Tornadus, Thundurus, Landorus, Skarmory, Drifblim, Pelipper, Altaria, Delibird, and Tropius.
Of these, many are not convenient to get, due to their location or their method of evolution. Eliminating those leaves us with: Sigilyph and Swanna. Let's weight them against each other.
Sigilyph
Pros
- It's found at a decent point in the game, just after the third Gym.
- Wonder Skin and Magic Guard are both very solid Abilities.
- Quite fast and has a nice Special Attack.
- Learns other moves like Ice Beam, Shadow Ball, Psychic, Energy Ball, Air Slash, Reflect... the list goes on.
Cons
- It's really a far better special attacker, with a higher base stat and better special attacks.
- Quite frail.
- Absolutely pitiful Attack stat will leave it missing out on the KO if you use Fly in battle.
Swanna
Pros
- Ducklett is found just before the Ground type leader, meaning that with a bit of grinding, you can bring in a powerful Swanna to combat him.
- Quite fast.
- Ducklett has a 100% encounter rate on Driftveil Drawbridge.
- Swanna can also learn Surf and Dive, making it a great HM slave.
Cons
- Swanna isn't that great in battle, due to below average stats in everything except Speed.
- It has a terrible movepool.
- The amount of grinding you would need to have one before Clay is a bit tedious.
Overall, I would say either Unfezant or Swanna. Unfezant is available early and uses Fly very well, while Swanna also gets Surf, which allows it to function as a reliable HM slave.
Now, you did say that any Pokemon Gens 1 - 5 is allowed, so I'll give you some more choices. I have no idea how difficult or easy these Pokemon are to obtain; I'm simply going based off their other merits.
Aerodactyl
Pros
- It's extremely fast.
- It uses Fly very well in battle, with a superior Attack stat.
- It also gets things like Strength, Crunch, and Iron Head.
Cons
- It's rather frail.
- It gets a lot of moves, but they're primarily Rock, Dark, Flying and Normal. The ones that aren't are low-powered or go off the Special Attack stat.
Hope I helped!