Would the flying starter be duel type in its earliest form, kind of like how Bulbasaur is Grass/Poison from the beginning? I would love that.
What type would you want it to be? Maybe we could make Flying starter start off as Flying/Fire, since people love Fire types and it would be extra weak against Rock, since Rock isn't really a great type since most of its moves have sub-par accuracy and it gets hit super effective by a lot of things.
How about: Flying starts off as Flying/Fire right off the bat. Doesn't learn good fire moves until it hits lv. 16 and goes to stage 2. Before that it only gets Will-o-wisp, much like how Bulbasaur goes a long while with only Poisonpowder as its poison move.
Rock type goes Rock/Dark at stage 2 because it's a rad combination, and Dark offers some higher powered moves with some accuracy.
Fghting stays Fighting until stage 3, where it goes Fighting/Grass and everyone complains that it's too much like Chestnaught until they look at its stats and see that it's fast and can go mixed (think Infernape), so Aura Spheres and Energy Balls all around. Make sure it has a couple decent coverage moves too, like Gunk Shot and Bullet Punch at the very lest so it isn't completely killed by fairies, which, considering this is gen VII, WILL be a thing.