Alternative app stores are not a problem on Android. There are lots of them. Alternative way to deliver push notifications is a problem. Currently, to solve it in a satisfactory fashion you need an alternative ROM to connect to a different push service.