Podrías probar a gestionar el buffer de salida de PHP.
Ejemplo:
Código PHP:
<?
// comienzo script tuyo
echo "Procesando ......";
flush();
// Tus rutinas actuales que se demoran en su ejecución ....
?>
Con flush() fuerzas a PHP a que envie todo lo que tenga en el buffer de salida al cliente (navegador en este caso). Normalmente y por defecto .. php entrega "todo" lo que va generando para la salida al final del proceso del script .. pero con esa función por ejemplo "forzamos" a PHP a que dé lo que tenga en ese instante .. y lo que entregará será en ese caso lo que salga por ese "echo" ...
Lo mismo puedes hacer incluso en tus bucles si los usas para hacer alguna especie de "barra" de progreso para indicar cuanto le queda a tu proceso por terminar ...
Un saludo,