Una cosa que se me ocurre es esto:
1. Pones al principio de todo, la primera linea, ob_start() eso hará que el contenido no salga en pantalla por el momento
2. Después de haber escrito todo el html, incluso cualquier cosa en PHP, al final del script, pones, $codigo_pagina = ob_get_contents(); eso hará que todas las salidas que hayas hecho en HTML, se guarden en esa variable, ya no van a salir por pantalla, serán almacenadas en la variable $codigo_pagina.
3. Ahora que tienes todo el código de la página, usas la funcion str_replace para reemplazar lo que quieras, en el ejemplo que has puesto sería algo así:
Código PHP:
str_replace("a", "e", $codigo_pagina);
lo sacas en pantalla con un echo, y ya tienes todas las letras cambiadas.
4. Después de eso pones ob_end_clean() y listo.
ob_start: http://es.php.net/manual/en/function.ob-start.php
ob_get_contents: http://es.php.net/manual/en/function.ob-get-contents.php
ob_end_clean: http://es.php.net/manual/en/function.ob-end-clean.php
Espero que te sea de utilidad, un saludo.