Оптимус Пьян

1. В начале работы скрипта ставите метку в БД, текстовик что работа началась, когда закончил работу то снимает метку
2. Cron запускается, смотрит метку, если метка стоит либо завершается, либо если вы уверены что первый скрипт скоро завершиться делает sleep 5,10,20 - сколько вам надо

Есть ещё вариант когда скрипт с помощью microtime сам следит за временем своего выполнения.

Только если у вас VDS на обычных хостингах нельзя
В скрипте set_time_limit(0);
В php.ini max_execution_time 0

Правильный ответ /var/spool/cron