Global Menus in multisite

I have 300 domains and thousands of subdomains on a single

multi-site install. The paying bloggers have access to all of them, so

they are shared blogs. The main content area features all the posts

from all the bloggers for any particular domain. All of the content

for all of the blogs is by default public. Any one can come read, but

only paid members can blog. I want the admin to set the top navigation

menus for every site within the multi-site network, but right now, the

navigation menus have to be setup manually for each of the 300

domains. I don’t want to hard code the navigation because it’s very

fluid and changes often. What can I do?