Btw, if alternative stores like F-Droid are not going to do it for you, you can always get your own phone whitelisted: https://www.google.com/android/uncertified/

Google is mainly concerned about uncertified phones being distributed at a large scale. For individual tinkerers, this feature is offered to get individual phones permitted.