Route 2:
Fletchling, evolves at level 17 to be able to battle in the sky
Pidgey, evolves at level 18 to be able to battle in the sky
Scatterbug, evolves at level 9 and evolves again at level 12 to be able to battle in the sky
Caterpie, evolves at level 7 and evolves again at level 10 to be able to battle in the sky
Burmy, evolves at level 20 and male to be able to battle in the sky
Route 3:
Fletchling, evolves at level 17 to be able to battle in the sky
Pidgey, evolves at level 18 to be able to battle in the sky
Route 4:
Ledyba, evolves at level 18
Combee, evolves at level 21 if female
Note: You can find Doduo on route 5 but it (or Dodrio) will not be able to participate in Sky Battles
Route 6:
Nincada, evolves at level 20 to be able to battle in the sky
Route 7:
Ducklett, evolves at level 35 to be able to battle in the sky
Ledyba, evolves at level 18 (berry tree)
Burmy, evolves at level 20 and male to be able to battle in the sky (berry tree)
Combee, evolves at level 21 if female (berry tree)
Spewpa, evolves at level 12 to be able to battle in the sky (berry tree)
Route 8:
Drifloon, evolves at level 28
Bagon, evolves at level 30 and evolves again at level 50 to be able to battle in the sky (grind if you want)
Wingull, evolves at level 25, found in hordes
Connecting Cave:
Zubat, evolves at level 22 and evolves again with high friendship
Santalune Forest:
Caterpie, evolves at level 7 and evovles again at level 10 to be able to battle in the sky
Scatterbug, evolves at level 9 and evolves again at level 12 to be able to battle in the sky
Fletchling, evolves at level 17 to be able to battle in the sky
Fossil Pokemon that can battle in the sky are Archeops and Aerodactyl
Hope I helped!
