I guess you'll be going for option 4 then
Within your <head>, you can include "site navigation links". The plan was that these would give user agents (ie browsers) a way to navigate the site without having to use the on-page menu. Unfortunately, the only browsers I've seen that actually implement this are Opera and Lynx. Firefox used to list the links but gave you no way at all of following them, but doesn't seem to even do that any more.
The way it works is that you list a series of link elements in the page head. eg
<link rel="home" href="/">
<link rel="next" href="article16.htm">
<link rel="copyright" href="/about/copyright.htm">
and so on.
The possible options for the "rel" attribute are: home, index, contents, search, glossary, help, first, previous, next, last, up, copyright, author.