Ciao,

la maximum_execution_time è un parametro settabile dal file di configurazione di php (php.ini). Di default è impostata a 30 secondi.
Ora i casi sono due: o hai la possibilità di accedere al file php.ini e modificare questo parametro (cosa che ti sconsiglio) oppure usi le funzioni ini_set di php per modificarne il valore.
Ovviamente su certi hosting non sono abilitate per questioni di sicurezza degli script.

Guarda questo link per la funzione che setta il time limit: set_time_limit()
Qualora tu non possa modificare questo parametro, l'alternativa nello sviluppare una newsletter è quella di spezzare l'invio delle mail (chessò 500 o 1000 per volta).