The main problem is probably that Flying is only a secondary type. Sure Bulbasaur had two types, but still. If it was Normal/Flying the elemental Rock-Paper-Scissors wouldn't work.
Then they can add another type for the flying starter. Water, Grass, Electric, and Dragon are all neutrally weak to both Fighting and Rock, and Electric and Dragon are neutral as far as attack goes. Make it one of them.
Which brings me to another point. Why is everyone so uncomfortable with a Dragon starter. Some people say Charizard should be changed to Dragon, and then everyone is like "OH NO HE'S GONNA BE TOO POWERFUL!!! I personally love Dragon and Ice attacks, so its not like I don't have anything super effective against it. And it only resists four types; Fire, Water, Electric, and Grass. Most Water types can learn Ice Attacks, so you can hardly count them. That's really pretty much only 3 types that it resists. Just look at how Steel is resistant to so many things, and tell me how Empoleon exists because of that logic...
The other problem is probably just that they're not that interesting. All of them are primarily physical types and none of them can really launch long distance attacks. Except for some very rare, usually powerful, moves.
You can almost flip that, though. Grass, Water, and Fire are primarily special, and proportionally there aren't that many physical attacks. The list is:
Grass: Bullet Seed, Leaf Blade, Needle Arm, Power Whip, Razor Leaf, Seed Bomb, Vine Whip, Wood Hammer
Fire: Blaze Kick, Fire Fang, Fire Punch, Flame Wheel, Flare Blitz, Sacred Fire
Water: Aqua Jet, Aqua Tail, Clamp, Crabhammer, Dive, Waterfall
For Grass, 2 out of 8 of them (Wood Hammer, Power Whip) fall into the category of rare and powerful. Leaf Blade and Needle Arm both before fourth generation, only existed as signature moves of specific families of Pokemon. Almost half of them didn't come into existence until fourth gen.
Fire has 2/6 Rare Moves (Blaze Kick and Sacred Fire), one of them being legendary exclusive. 2/6 of them came in the 4th gen.
Water has 2/6 Rare Moves (Clamp and Crabhammer) and 2/6 that come from 4th gen.
Why can't you just introduce a few more special Rock and Fighting moves (Flying is almost good with 5, and 4 of them are not Aeroblast) and it would be almost even. They've proven that they'll go against the norm with the normal three elements recently.
The flying/fighting/rock combo WOULD work. I'm trying to think of other "triangles" that would work. The one that came to mind was water/electric/ground, but that doesn't work because of the immunity that ground has to electric. I'm blanking on other triangles that could work.
I think that might be the only other triangle that could work with solo types, but it would mean that they would have to make flying its own type for the first time ever. However, I'm sure they could find quite a few more with dual types.