It is common to have a heading that applies to a level above the document level. For example, in this screenshot of a New York Time's headline, "Middle East" is the category which is above the page level. Obviously, "Even Gaza..." is the heading of the page. 
My question is, what is the best way to mark up "Middle East"? The nytimes devs chose to use an h3 but this seems like it might not be best. It almost seems like it would need an h0 tag.
I'd love to hear opinions on this. Thanks.
(Assuming HTML5.)
The whole article should be placed in an article element.
This article "longs" for a heading. Of course it should be the actual title ("Even Gaza […]"). You could either use a h1 or the appropriate rank depending on the nesting level of the article element (e.g., h2 if it’s a child of body); the latter is encouraged.
So now we have:
<article>
<h2>Even Gaza Truce Is Hard to Win, Kerry is Finding</h2>
</article>
What to do about "Middle East"?
Currently, the document outline is:
1. untitled (→ should be the page/site title)
1.1 "Even Gaza Truce Is Hard to Win, Kerry is Finding"
Makes sense.
If you would use a heading for "Middle East", and place it before the article heading, the outline would become:
1. untitled (→ should be the page/site title)
1.1 "Middle East"
1.1.1 "Even Gaza Truce Is Hard to Win, Kerry is Finding"
Can make sense, but I’d only use it for a page listing several articles categorized under "Middle East" (in which case the "Middle East" should be the heading of a section with article children).
If you would use a heading placed after, it would become:
1. untitled (→ should be the page/site title)
1.1 "Even Gaza Truce Is Hard to Win, Kerry is Finding"
1.1.1 "Middle East"
Doesn’t make sense.
So I’d not use a heading for "Middle East" if this is a page containing only this article. Instead, you might want to use markup described in Subheadings, subtitles, alternative titles and taglines:
Use a header element for the category and the article title; that way the category will not change the document outline and it’s clear that its part of the introductory.
<article>
<header>
<div>Middle East</div>
<h2>Even Gaza Truce Is Hard to Win, Kerry is Finding</h2>
</header>
</article>
The author (as well as the share links) could be placed in a footer element:
<article>
<header>
<div>Middle East</div>
<h2>Even Gaza Truce Is Hard to Win, Kerry is Finding</h2>
</header>
<footer>
<div>By Michael R. Gordon</div>
<div>Share: …</div>
</footer>
</article>
So everything else (i.e., not in header/footer) in this article is considered to be the main content.
I think that "Middle East" needs to be treated like a Tag or Category. In the same place you can have multiple tags like "Latest News" or "Palestinian crisis" and so on.
I don't think that is a good idea to markup this elements with a H1, it's not the main element, it's more an "attribute" of the main element that is the news title "Even Gaza Truce is Hard To Win...".
So you can tag it with a H3..H5 with a special CSS class like "newscategory", or "geocategory".
Just my 2 cents..
On that NYT webpage, the "Middle East" you referred to is used as a link to a Middle East webpage. So "Middle East" looks like a heading but also provides navigation.
Knowing that, I would not make "Middle East" any type of heading (HEADER, H1, H2, etc.), but would instead put it (and the A tag it is already in) inside a NAV. This alternative avoids the heading level confusion.
