By this I mean that you keep your jobs in Postgres, but instead move the ordering -- the physical queue data structure -- out into something like RabbitMQ or Redis.
To schedule a job, create a job row, then push its ID to Rabbit or whatever. To process the next job, grab the next ID, look up the job row, then do the processing.
That gives you the best of both worlds, without ever running into issues with locking and dead tuples.
(There is of course a race condition here where you may create a job but not publish it (due to Rabbit temporarily failing, for example). But there are ways around that.)