Sending mobile push notification to a large amount of users spread over time

We have a mobile app and we want to send a mobile push notification to about 1,000,000 of our users.

Our requirements are:

• Every user can have up to 4 device tokens (2 Android / 2 iOS)
• We would want to send the exact same message to all users
• We would like to spread the push over a long period, so it doesn't get sent all at once and cause a massive influx on our servers
• We would like to find a highly reliable way of doing so
• We have said tokens stored on our database, but not connected to any 3rd party setup

We've tried using PushSharp, but it isn't too reliable for high volumes. We've also tried using Amazon's SNS, but they have a very limiting throttling rate on their registration API - and it would have taken us about a week just to register said device tokens to their system.

So in general, we're looking for a good code or 3rd party solution for this issue.

Thanks