F-Droid is not doing too bad. And yet, the vast majority of people will never ever use it after Google Play implenents their developer verification scare screens.
None of your examples succeeded in an environment that was even remotely as hostile, neither Windows nor Palm could have done what Google does today, without risking a fatal user backlash.
It's one thing for something to be thinkable and imaginable. Of course you can imagine Google Play getting dethroned. It's just so incredibly unlikely to happen without regulatory antitrust intervention that it is pointless to consider seriously.