What if the permission enablement was made more difficult? Perhaps like how you get to access Android developer tools only after tapping the build number a bunch of times. Or even, making it something you have to run from a CLI while connected to a computer.
My point is, there are many options that preserve safety for the vast majority of users without making it a total non-starter to use alternative app stores.