You're still racing between the select and the update, although something like this might work:
This way you're letting the database server handle updating the correct records. Depending on how speedily new records are added to the queue, it seems likely that processes will be working with records more than waiting for selects. Of course this approach doesn't help with splitting the records evenly between processes, but neither will a mutex.