It would be very difficult to code a solution that would work with any arbitrary site out there. Each navigation menu implementation can be quite unique. I've worked a great deal with scrapers, and, provided you know the site you wish to target, here is how I'd approach it.
Usually, if you analyze the particular javascript used in a nav menu, it is fairly easy to use regular expressions to pull out the entire set of variables that are used to build the navmenu. I have never used Beautiful Soup, but from your description it sounds like it may only work on HTML elements and not be able to work inside the script tags.
If you're still having problems, or need to emulate some form POSTs or ajax, get Firefox and install the LiveHttpHeaders plugin. This plugin will allow you to manually browse the site and capture the urls being navigated along with any cookies that are being passed during your manual browsing. That is what you need your scraperbot to send in a request to get a valid response from the target webserver(s). This will also capture any ajax calls being made, and in many cases the same ajax calls must be implementated in your scraper to get your desired responses.