Hola,
Para aumentar el tiempo maximo de ejecucion para un script es con la funcion set_time_limit() (
www.php.net/set_time_limit). Y si no puedes modificarlo, la solucion seria "paginar" el envio, es decir, hacer que el script envie solo x emails, y cuando finalice que se redireccione a si mismo para enviar los x siguientes.
Saludos.