This is what I have for Mega Pidgeot, if anyone can fill in blanks (like the requirements for the Pidgey in regards to nature/iv's, or if Blue has even more mons possible for his team), please do:
In Viridian City, cut the tree on the top left and go through until you see the flying type lover, somewhere far left. Beat him and his lv. 10 pokemon, talk to him again after the battle, he will then ask to show you how a real pokemon master trains a Pidgey.
Catch a good pidgey (not sure how many iv's are required since mine has 154) and show it to him, then train it up to a high level with maxed ev's.
Mine was level 98 with ev's in speed and sp.atk (and choice scarf to outspeed him). His Pidgeot will be level 80 and physical. You can only have this Pidgey in your team for this battle. As far as I know, you cannot evolve your Pidgey for this, but if anyone can contradict this with proof, please do.
After winning, you have to go to Indigo Plateau (past victory road, right building) and talk to Blue. Show him the Pidgey and battle him (you can use your full team here). His line-up will be randomly selected from Gyarados, Exeggutor, Alakazam, Rhyperior, Tyranitar, Machamp and Arcanine (and possibly others, I only fought him twice), his last one will always be Mega Pidgeot. The order of his mons will be random except Pidgeot and from what I saw they all have Life Orbs. If you lose, there is NO cooldown.
After winning, go back to Viridian City and talk to the Flying Type Lover and show him the Pidgey once more. Then you finally get the stone
ps: Mega Sharpedo is missing from your list.