Yeah, what a significant boost in defenses...
Starmie Base stats: 60/75/85/100/85/115
Greninja Base stats: 72/95/67/103/71/122
20 points higher in Defense is pretty significant. Especially in this Meta-Game with a whole lot of physical attackers.
Starmie is psychic type, which is not good in the metagame. Aegislash, Tyranitar, Scizor, Genesect (post-pokebank) and Rotom-A are all extremely common pokemon that starmie gets flat out countered by. Greninja can at LEAST u-turn out.
This is true. U-Turn is a great move for Greninja to have and can get him out of trouble.
Starmie just BARELY takes a Brave Bird from Talonflame:
252 Atk Life Orb Swellow Brave Bird vs. 0 HP / 0 Def Starmie: 220-259 (84.29 - 99.23%) -- guaranteed 2HKO (75% chance of OHKO if Stealth Rocks are up)
And Greninja CAN'T survive a BB at all from Talonflame. That is a big difference. Starmie can survive and Thunderbolt or Hydro Pump in retaliation. Greninja just dies. XD
Just because you have protean doesn't mean you can't make intelligent plays, and with 122 speed, what can really hit you with these attacks other than scarfs and priority? Greninja's Ice Beam OHKO's Dragonite through multiscale. Starmie cannot do this.
You are right, however, your opponent can also trap Greninja slacking and kill it off afterwards due to a new-found weakness due to Protean. Now, Protean is still a great ability, but I do not find it the be-all end all. Especially since it changes the moment you pick the move, and not after the move is used, which is both good and bad, IMO.
So does Greninja. It gets Grass Knot, U-turn, Dark Pulse, Extrasensory, Spikes, Hydro Pump, Toxic Spikes, and can go physical as well. Keep in mind that these are all STAB.
Greninja cannot learn Psyshock, and Extrasensory wishes it was as good as Psyshock. Starmie can also learn Grass Knot, however the coverage options are better with Starmie's other moves (same with Greninja, actually...) Using Spikes for set-up is dangerous against a lot of threats due to the lacking bulk and defenses of Greninja. Having a ground weakness is also probably not the best thing to have, either. The best thing about Greninja is STAB everything. It is what makes him really dangerous, and OU material, but I really don't think it out-classes Starmie by a whole lot overall. Both have their purposes.
Yes, Starmie will have this niche, but I don't think that's enough to stay relevant in OU. It wasn't so much that rain was nerfed, moreso that the metagame around it changed. Starmie's still a pretty good pokemon, but I have difficulty justifying its spot on my team when Greninja is a better attacker, and Excadrill is a better spinner in general.
Excadrill is easily the best Spinner, I agree, but Starmie has that needed speed to make sure those hazards are gone and still chase out or kill a few pokemon. Also, Timid Starmie I believe outruns Modest Greninja. You could run a Timid Nature (in turn limiting how hard it will hit), or Scarf it, but getting trapped in one move may not do Greninja any favors and is probably still better off with Life-Orb.