Semantic HTML5 structure versus CSS layout needs

Question 1

I am running into the same conundrum as you, and I appreciate the frustration. I will attempt a negative answer, because I feel both of these positive ones (which say you can achieve both your ends) are missing the point.

Firstly, the way I see it, your principle difficulty is that CSS cannot move an element to a new container. The two answers fall into two categories:

Some are ultra-specific hacks (subjectively speaking) involving floats, negative margins, and/or absolute positioning which can move an item presentationally out of its container. These can be effective, but only in very specific cases. As your needs grow, it becomes difficult to maintain and it requires putting a rather large thinking cap on to address each new need or edge case that you had missed earlier. The answer by @jennifit attempts to move you in this direction. It is, I believe, the normal route taken by those trying hard to follow the spirit of semantic HTML5, which is admirable. But it can be a quagmire that makes you begin to ask exactly who you're maintaining your semantic purity for? Is it for the search engines, the screen readers, or ease of maintenance? I'll get back to this after the next classification.
Some are pragmatic rationalizations that claim to be equivalent semantically but are, in truth, a different semantic meaning. These are really semantic hacking in my opinion. @volker-e 's answer is an instance of this. He's right, this is an alternative markup that could work -- but, it doesn't equal the same semantic meaning. The h2 belongs in main as an h1 -- it makes no sense to move it within the page's header. In fact, you're saying that your heading is unrelated to your main content. This, in some ways, is worse than using that div you wanted to use, because you're making a false semantic relationship by grouping the page-header and site-header into the same semantically-significant header. A semantically meaningless container, such as div, for both header and main, is actually less perverse in my opinion.

So, getting back to what I said about who you're maintaining semantic purity for, this is the real philosophical question at play. There is often an obvious, effective, and maintainable solution without rationalized mis-uses of existing semantic elements or css 'tricks'. In your case, of having an item which is semantically a child but presentionally not a child, the answer is the one you've already put forth as a question:

Rewrite the HTML5 markup with non-semantic elements (e.g. divs) so that it corresponds more to the visual layout and then exchange the non-semantic elements by[sic] semantic ones (e.g. footer or main) wherever possible with the new structure.

This is the right thing to do whether you're semantic-purity was intended for

accessibility: in this case you can achieve that in a non-hierarchical way with ARIA roles.
search engines: search engines still understand the old way to do things, so you're not going to get into SEO trouble if you follow older approaches to semantics.
maintenance: this is the reason most people are lured in by -- but the problem is, what's the point of maintainable HTML but unmaintainable CSS, or the other way around? you have no choice but to see your maintenance as a combination of both CSS and HTML, and you have to find the middle ground where they are both deranged equally when you run into a difficult presentational problem.

The only other possible answer, if you feel that HTML semantics are all that matter, is to accept the limitations that hierarchical HTML semantics places on your layout. The problem is, there is no way in CSS to re-create the layout hierarchy. Until that happens, you'll have to accept that HTML is both a presentational and a semantic language, and, therefore, semantics will always be a matter of "better" and "worse". Truly beautiful or rich or perfect semantics will be unachievable in many, if not most, layouts.

Question 2

My approach would be the following:

<!DOCTYPE html>
<html>
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
    <a class="aural" href="#content">Jump to content</a>
    <header role="banner">
        <h1 class="site-logo">Logo</h1>
        <nav role="navigation" aria-labelledby="nav-heading">
            <h6 id="nav-heading">Navigation</h6>
            <ul>…</ul>
        </nav>
        <h2 id="heading">Page heading</h2>
    </header>
    <main id="content" role="main" aria-labelledby="heading">
        Page content
    </main>
    <footer role="contentinfo">
        Content information
    </footer>
</body>
</html>

and then go for a CSS ruleset like:

header h1,
header h2,
header nav {
    float: right;
}

Diff:

You have appropriate accessible headings for page's content
You save otherwise seemingly useless div in header & main
You've got a nice HTML5 structure outline, which helps SEO.
I've included (was not part of the question) the navigational landmark roles as of WAI-ARIA 1.0 draft specification
I've included a skip link, which is still recommended best practice
Minor change: I know, charset value case is insensitive, but as you also write DOCTYPE uppercase, UTF-8 is the more correct value, see http://en.wikipedia.org/wiki/UTF-8#Official_name_and_variants

Question 3

The first structure may still work if there is position:relative in < main > and using position:absolute on h1 with a z-index and a -ve margin. That way, the heading will always float on top in the same position in relation to the main content. While it may not be the best solution, I think it will not break the layout (?)