Hm, personally I wouldn't hide anything.
Maybe playing with CSS to move the menu deeper down in the HTML, while visually maintaining the same position; or even making a full separate page with the menu, which will be robots disallowed?

__________________
Impossible? You just underestimate the time.