Io vedo una gamma abbastanza limitata di soluzioni:

1)
crei uno script in un altro linguaggio che possa essere ingaggiato in qualche modo da PHP ma facendo in modo che la pagina PHP dia solo l'avvio alla procedura, restituendone lo stato tramite la stessa o un'altra pagina;

2)
suddividi il tuo batch in "gruppi" di elementi da elaborare (record o altro) usando AJAX per invocare la pagina e ottenere il risultato dell'elaborazione di quel gruppo, tendenzialmente piccolo e senza rischio di timeout; all'avvio di ogni procedura, a fronte della risposta si passa a eseguire il gruppo successivo e così via, fino a esaurimento dei gruppi di dati da elaborare (di cui puoi tenere sulla pagina lato client anche solo gli indici o i riferimenti); questo approccio consente anche di aggiornare contestualmente anche la pagina in modo dinamico, mostrando di volta in volta i gruppi che vengono elaborati, ma richiede ovviamente esperienza nella manipolazione della pagina con il DOM o con JQuery o altro framework.