si, mejor empezar a usar PHP para hacer webs dinámicas, en HTML es lo que tiene, que es manual...
La otra opción (fácil) es la que comentas de meterlo todo dentro de un javascript y lo llamas.
Me han comentado que poniendo el codigo del menu en un archivo .js, luego puedo en la celda (donde va el menu) poner una estiqueta script para que me muestre el contenido del js, y asi si tengo que modificar el menu alguna vez solo tendria que modificar el menu en el js y no en todos los html.
Por ejemplo, en todas las páginas HTML añades el código:
Y en el script codigo.js añades lo que quieres mostrar:
document.write('código');