On Androids, I think you can install third party appstores. fdroid is the one I've heard before, but there could be more.
As mentioned this is possible but not recommended for Android. I'm not sure if anyone is releasing paid apps outside of Play store though.