Devi entrare nel meccanismo di come lavora una pagina web generata in PHP.
Innanzitutto header("Location: pagina.php"); non mostra una nuova pagina: indica al browser che, quando ha finito di caricare la pagina corrente, dovrà caricarne un'altra. E per dire di aver terminato il caricamento della pagina corrente dovrà attendere una "risposta definitiva dal server", il quale la darà solo dopo aver concluso tutte le operazioni, incluso l'invio della mail.
Diverso è invece mostrare effettivamente la pagina, senza redirezione, prima di inviare la mail:
Codice PHP:
include "pagina.php";
flush();
mail($dest, "Oggetto", $messaggio, $intestazioni);
non è la soluzione più intelligente del mondo, ma mi sembra l'unica percorribile se intendi simulare un comportamento asincrono in PHP.
Altrimenti c'è appunto AJAX. Nasce apposta per realizzare operazioni come quella di cui hai bisogno, non c'è ragione di rinunciare a utilizzarlo, soprattutto da quando librerie come jQuery lo hanno reso ancor più semplice.
Esempio preso dal manuale.
Quale manuale consiglia questo? Tutti gli esempi che ho visto su PHP.net bloccano esplicitamente l'esecuzione dello script con una exit dopo aver inviato un header location (il che ha senso: se intendi forzare lo spostamento verso un'altra pagina che senso ha continuare l'esecuzione dello script?).