Cудя по описанию вы используете реляционную базу как очередь задач/сообщений, что есть антипаттерн...
По теме - используйте функцию connection_id:
-- Все это надо сделать в транзакции
-- Сначала захватим строчку, пометив ее своим уникальным идентификатором
UPDATE tblName SET locked=connection_id() WHERE locked=0 ORDER BY dateColumn LIMIT 1
-- Получим данные (предварительно захваченную строку)
SELECT * FROM tblName WHERE locked=connection_id()
-- Удалим за собой
DELETE FROM tblName WHERE locked=connection_id()
