Well, what about the EU browsers solution? Google could still have its own app store, but instead of being pre-installed and integrated, the user would have to select one or more during the initial system configuration (and have a menu for changing that later).