Как сделать, чтобы меню навигации было на каждой странице, но не прописывая его каждый раз в новом html?

что это значит?)

Можно и js`ом подгружать менюшку

Станислав, дикий оверхед

Dark Hole, смотря какое меню, и где оно расположено. У меня на одном из сайтов вобще полностью формирование менюшки с категориями идет с помощью js и никто даже не догадается об этом =)
Ну а если все по стандарту, типичная менюшка, то да, не прокатит. Но и слово "Никак" неуместно =)