Welcome to WebmasterWorld Guest from 18.104.22.168
Forum Moderators: goodroi
Detect the HTTP_User_Agent, and if Google, do not include the nav bar. You'll also want to use the robots-nocache meta-tag to prevent these modified pages from appearing in Google's cache.
It also might be a good idea to leave an html comment in each page briefly explaining why the page served to Google is different from what a user sees, in case you're in a competitive market where a competitor might report you for cloaking... Just a thought.
Robots.txt won't be of much help here, for the reasons you cite and others. Robots.txt works at the URL-level, and not at the "file" level, so it won't help to disallow the files you include in each page on the server side.