Actually, when you NOTIFY a channel in Postgres it gets delivered to all clients who have previously run LISTEN on that channel. And you can send an optional payload (up to 8000 bytes):
Oops, my mistake. That's actually disappointing, since it means that for every message, N workers will all wake up and needlessly try to grab the message.
You can get around that by using advisory lock to make access exclusive, but they will still all wake up and will still have issue a select.
Why not have N channels for N listeners? These are very lightweight (no persistence/retry, etc. -- essentially just a way to avoid SELECT polling by consumers).
That ties the channel names to the number of listeners, which opens you up to race conditions when the pool of workers changes. And you would have to keep track of which channels aren't busy at any given time, in order to avoid waking up busy workers that can't accept a job. Not impossible, just more stuff that could go wrong.
I think you're right, that would need to be built into whatever job management logic you implemented before the notification was sent. This type of architecture is more suitable for a workflow or job management system rather than fanning out data processing to N workers.
http://www.postgresql.org/docs/9.3/static/sql-notify.html