The best Fly user in Black 2 and White 2 is Ducklett, which also learns Surf and is a guaranteed encounter on the Driftveil Drawbridge. This means you can catch it after earning four Gym Badges. If you don't think this is early enough, your other two options are Pidove and Zubat, which arrive at Route 20 and the Castelia Sewers respectively.
I think Ducklett is better than Pidove because it learns more HMs. Crobat is stronger if you want a Fly user that can actually perform well in battle, but mind its long Friendship evolution. You will also need to find a different Surf user if you forsake Ducklett.
The Braviary/Mandibuzz on Route 4 are also options if you need a Cut user or a reasonably strong battling Pokemon. They're definitely better than Pidove at least.