users are not gonna download the app unless many services are using his api, and not many services are gonna use his api unless there is a big user base ... sounds like a prime example of chicken and egg
That's why I don't see the chicken-egg problem.
If I install any app, I do not expect to have to download dependencies to make it function fully. To that end, this solution is useless.
My outlook is simple: there are native implementations of push notifications on mobile devices. It may cost time and money to set them up, but please spend some time implementing them.