I have to build this soon too, my guess is that for scalability something like option 2 with sharding users into buckets based on some hash would be the way to go.

Actually scratch that last answer. You don't even need to do any of the above, you can store the platform endpoint ARN on your server for every user and just send notifications to that ARN when you have a notification for that user.