Ich würde so machen:

Ein CGI-Script stößt ein anderes Script im Hintergund an, welches sich um das Starten des eigendlichen Prozesses kümmert. Die PID des Scriptes wird in einer Datei zwischen gespeichert. Über "autoreload" wird wird das CGI-Script neu geladen welches "Bitte Warten" anzeigt solange die in der Datei gespeicherte PID noch existiert.
"autoreload" wird erst dann aktiv wenn die Seite vollständig geladen ist. Das bedeutet nach dem ersten neu laden lässt man das CGI-Script solange aktiv bist der Hintergrundprozess beendet ist, Danach übergibt mit dem Script man eine Weiterleitung.