do you not think that they also aid in-page navigation for screen reader users?
They can; header-navigation is one of the easiest ways to bop around in a page. But I agree with Tyssen: you're overdoing it here. People have access to the beginning and end of the page: the skip links are the first content on the site; heading them is unconventional and unnecessary.
I don't "head" my skip links and I usually don't "head" my main menu (unless, as Tyssen mentioned, there are other menus... complex sites may have a "main" navigation menu (which I would give a role of "nav" to), a "sub" navigation (less important but still site-wide links, like privacy, terms&conditions, press releases, investor relations... and this nav might be in the footer), a "products" menu for sites who sell many products, etc) because, as Tyssen said, the main menu is fantastically obvious and users have numerous ways of navigating it. Headers are Good, but Being Too Chatty can reduce accessibility. There's a clever term for this (too much accessibility) but it escapes me. In any case, it can become annoying quickly.
Users who want to get straight to the main content have many options:
-they can use your skip links (see Safari note below); so make the link text obvious that it's for skipping
-they can call up all the lists of links on the page, and select the second one (main nav) and then Next Non-Link Text (this would be your h1)
-they can use h or h-1
-they can go directly to the role of "main" that you'll have on your content div
-they can go do the role of "nav" and then Next Non-Link Text
Lots of options. Most sites don't head skip navs or main navs, meaning these other methods of moving around them aren't lost on experienced users. I would expect less-experienced screen reader users to use the skip links heavily... so a link to your footer would not be a bad idea. Also, skip links are still pretty cool for sighted keyboarders... so have that text appear onscreen on :focus.
A note on the "using skip links to move focus down the page": this won't work in Safari, which means it won't work for VoiceOver users who don't use Firefox or some other browser. Safari moves the visual focus down when clicking on a skip link whose destination is an id attribute, but it won't move the keyboard focus. If you want to ensure VO users using Safari get real skip links, you'll need to embed something clickable at the skip destinations. I use empty anchors inside the elements whose id's the other browsers are using.
Opera sometimes won't do this either, but I forget the rule for Opera (and I worry much less about skip links in Opera: it's trickier to use with many screen readers and Opera offers spatial navigation for sighted keyboarders, meaning they have more freedom to move where they want than users of other browsers).
I personally would say heading the skip link nav is Too Much and heading the main nav is being Captain Obvious.
Having a skip link to your footer is good/fine if there's a nav in there, using role=complementary is good, heading it is something I'd only do if I had a Fat Footer (those ginormous things people manage to call footers but are like half the site page crammed with information... and may have multiple headers inside them!).
This would not alter its screen position but I have major reservations about this unconventional HTML layout that would not match the screen layout.
While I agree with your conclusion (don't move the main navigation to an unconventional order in the markup), whenever you start playing with position: fixed, that kind of talk gets nowhere fast, because screen layout becomes disconnected with any sort of reality anyway. I had a layout with main navigation in a fixed footer (but also, really in the footer) and even setting up skip links at the start of the page, I was pretty sure people would get confused. I just didn't have any authority to re-arrange that page though.