You're still racing between the select and the update, although something like this might work:

• Update records where 'owner' column is null, with *my* value and timestamp now().
• Select records with my owner value *or* where timestamp is older than threshold. This catches the case where some records have gone stale because a process died or what-have-you.
• Process & delete selected records.

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.