In Britain we'd say
He had a black hat on.
Speakers of American English are more likely to say*
He had on a black hat.
The latter just seems wrong to me. Is my intuition correct or are both equally valid usages?
* - according to Google NGram
You did notice that something is different between American and British usage of "have on a hat". Let me show two Google Ngrams that illustrate the situation.
In British English, pre-1960, "had on a coat" is the most frequent of these expressions, followed by "had his coat on". However, "had on a coat" drops in frequency by a factor of nearly 30 by the 2000s.
In American English, these same two phrases are also the most common, but remain so for the entire period.
(Don't ask me why the most likely order of the preposition and the object depends on whether you use "a" or "his"; this is a piece of grammar that I obey, but I have no idea why. But either order is grammatical with either "a" or "his" in the U.S.)
To answer some of your questions:
(1) I think Americans are roughly equally likely to say "had a black hat on" and "had on a black hat". However, you are only noticing the second one, because this is a usage not found much in England anymore.
(2) If something was grammatical 50 years ago, I think it's a stretch to say that it is actually incorrect today. But you are right in that "had on a black hat" seems to be falling out of use in England.
What is going on here? To have on meaning to wear is a phrasal verb (Wikipedia link) made up of a verb combined with a preposition1. For many phrasal verbs, the object can go either before or after the preposition. For some, like to tell apart, the object can only go before the preposition. For others, like to take after, the object must go after the preposition. What I suspect is happening is that, in England, to have on has changed (at least among the younger people) from the first kind of phrasal verb to the second.
1 This preposition is sometimes called a particle because it does not behave grammatically like a preposition when it is part of a phrasal verb.