secondo me ti conviene adottare la prima soluzione alla quale hai accennato; distingui l'header dal menu.
Inoltre, dopo che hai realizzato la pagina, prova ad eliminare il css
(con dei commenti) e vedi se la pagina stessa si "trasforma" in righe fruibili anche da browser testuali.
ciao