А почему не обрабатывать по одной записи? Тогда можно делать захват строки атомарным запросом:
UPDATE `table` SET `updating` = NOW() WHERE ... AND `updating` IS NULL AND @id := `id` LIMIT 1;
SELECT * FROM `table` WHERE `id` = @id;
После обработки снова выставить `updating` на NULL. Периодически сбрасывать `updating` у строк, обработка которых продолжается слишком долго и, скорее всего, сбойнула.
При такой выборке параллельно обрабатывать строки может любое количество одинаковых скриптов.
