Hola Orgueira:
Con respecto a los menús, tu lo has dicho cada uno tiene sus preferencias, todas las que has indicado son válidas.
En mi caso uso un menu que se repite en todas las páginas, si lo quieres ver lo tienes
aquí , pero es muy agil.
Con respecto a repetirlo en todas las páginas basta con hacer la llamada al archivo js. pero el menu en si solo lo escribes una vez.
Si te decides por los frames(eso va a gustos), también hay muchos, ya nos comentarás y te facilitaríamos alguna dirección.
Un saludo.