se non puoi impostare il timeout dello script potresti pensare di dividere l'esecuzione in step richiamabili via GET (script.php?step=50, script.php?step=100, etc...)

in base ad $_GET['step'] Limiti la query ad X email
Codice PHP:
$ciclo 50// Mail da inviare ad ogni ciclo
$end = (int)$_GET['step'];
$start $end $ciclo;

mysql_query("...... LIMIT {$start}{$end}"); 
Poi puoi gestire il redirect al prossimo step con JS
Codice PHP:
echo '
<script type="text/javascript">
<!--
function Redirect() 
{
   location.href = "script.php?step=' 
. ($end $limit) . '";
}
window.setTimeout("Redirect()", 300000); //Fa partire il redirect dopo 5 minuti
//-->
</script>'

Certo, devi lasciare il browser aperto finche hai finito, però credo possa funzionare