Я бы делал небольшого отдельного демона/скрипт/whatever, который стартует из-под крона с какой-то частотой, проверяет блокировку (flock-ом, на крайняк), лезет в базу, понимает, какие ему сейчас надо выполнить задачки, запускает child-процессы для их обработки (тут можно и аппетиты ограничить, если надо), отмечает в базе, что процессы запущены, освобождает блокировку и мрёт. Это если погрешность в одну минуту - не смущает.
Если смущает - отдельный демон, который слушает, например, сигналы ОС, и по прибытию сигнала от php-приложения или своего собственного аларма, проделывает вот это всё из первого абзаца, только сперва отключив обработку сигналов ;). При стартек демон пишет свой pid куда-нибудь, чтобы ваше приложение знало, кому сигналить. ;)