When The User Need It
And your first thought is "No Sh*t Sherlock!"
Let's put your circumstances and resources on the side for now and talk about the optimal experience.
A feature like notifications is an additional value to enhance the user's experience but is not needed by all of your app users.
The following image comes from a content marketing blog post - no endoresment i just googled it. It refers to customer acquisition funnel, which explains the different modes that your users might be at:
Consideration & Intent Users
It is important to realize that when a user downloads an app they did not necessarily try it yet, therefore did not see the value yet, therefore do not need it yet. So the chances of needing the notifications are low. Instead, they will likely avoid notifications, fearing spam or such...
Some users have downloaded the app, but currently trying it out. At this point, they probably want to avoid commitment, which is most likely the reason the would reject giving the permission.
By purchase, it does not necessarily always mean money, but by choosing that this is a product that I - as a user - want, and I will be using it from now on.
A user at this stage is much more likely to try/use/need an additional value such as the notifications, which is a great segment to focus on.
So if you know at which stage is your user, you will know when it is the best to offer it again.
And knowing at which stage is your user, will help you a lot with decision making, not only at features like notifications but also all the way up to the business decisions.
But in reality, we have limitations, could be resources, could be policies or other factors. And that's when we start looking for tips and tricks to solve these problems, knowing that they won't be the perfect solutions, but will increase the chances of working things out:
1. Try the web notifications for a week
When a user rejects the notifications, a common concern is that he fears spam, ask him again with limited time, and show him that it is easy to cancel this, if he likes it, next week he just has to either confirm or opt out.
2. Ask again in X time
You can ask again in one month, one week, after using the app 10 times, it depends on your user, the app, and how much value will notifications bring.
3. The bait
Don't ask him for the notifications, let him ask for it
download bmml source – Wireframes created with Balsamiq Mockups
The list carries on, you just need to brainstorm more ideas and i'm sure you will figure it out