-Caso eu precisar alterar o menu, por exemplo, eu teria que modificar o código de todas as páginas criadas até então.
Por isso eu falei do uso de includes. Você já pesquisou sobre isso? Já fez testes com includes?!
-O site será renderizado toda vez que eu abrir uma nova página de conteúdo. O que pode deixar a navegação mais lenta.
Não. Visto que os *.js, *.css e afins já estariam no cache da máquina.
Posta tua dúvida no fórum de PHP, sobre os includes, se você ainda não entendeu sobre esse ponto.
Mais um link para ti pesquisar: http://www.w3schools.com/