I've spent a fair amount of time looking at Ruby based push notification solutions. The best one is RPush https://github.com/rpush/rpush. RPush is very well tested at this point (We use it to send millions of notifications), and handles a lot of difficult edge cases well. I wouldn't recommend building your own from scratch since there are so many potential pitfalls and edge cases. RPush doesn't support Pebble or Web App notifications, but could be extended to do so.
If you decide to explore other alternatives, make sure they:
Handle closed connections gracefully for APNS - In many cases, Apple may close the connection to their server, and your push notification library must handle this correctly otherwise thousands of subsequent notifications can go undelivered
Communicate with Apple's feedback service - Apple requires you to poll one of their endpoints for a list of devices to stop sending notifications to. If you fail to do this, you can get rate limited.
Can send notifications at a fast enough rate for your requirements.
Outside of Ruby, the best push notification libraries seem to be PushSharp (C#), and Node-Apn (NodeJS, iOS only)
Finally, it sounds like you have specific needs that require you to do this yourself. But for others, I would strongly encourage you to use a 3rd party services. Reliably sending push notifications at a high volume is difficult and there are many 3rd party services that will do it for you at low cost. For instance, UrbanAirship, Parse, and OneSignal (My service) are all great 3rd party solutions.
Update to address revised question:
The best design pattern is to have a a second daemon process or Cron Job that handles message delivery. It's not practical to try to do this inside of a Ruby on Rails application.
The RoR application can insert rows into the Notification table as a queue like you describe. Then the daemon process or cron job can fetch notifications from the queue and deliver them.
If you use RPush, this is the pattern that it follows. It comes with both a Gem to load into your Rails application that inserts notifications onto a database queue, as well as a daemon that you keep running on your server that periodically checks for new notifications to send and delivers any that get queued up.