I just realised something very interesting in your question that changes the answer I would have given earlier. The way I first read the question — ‘Is Herr Hitler valid German?’ — calls for a very short and simple answer that Hubert has already given: Yes, it is perfectly valid to address everybody, be they head of state/government or tramp, descendents of nobility (abolished 1918) or a cleaning person with Herr/Frau and their name. It’s the expected polite way to talk about strangers.
But then I noticed that your question reads:
Would Herr Hitler have been valid German?
and alongside with Gerhard’s comment I noticed you might have been asking for something different.
The general point still stands whether the year be 1938 or 2015: addressing the head of state as Herr Gauck or Herr Hitler is correct, polite and not too formal. Neither Hitler nor Gauck are or were of any branch of nobility to the best of my knowledge, so the addresses would not be convoluted by anything that was lawed out of practice in 1918.
But in 1938 nobody in the Reich would have said Herr Hitler openly — and if they had, the Gestapo would have started watching them closely. Hitler loved to be addressed as Führer und Reichskanzler or just simply Führer — a title he created more or less for his own use so he could feel more noble. This title spread across everyday usage and people would use Mein Führer to address him — or der Führer when talking in third person.
Actually saying Herr Hitler — or worse, addressing him as such — would have demystified the character propaganda had built up, reducing him from being the ‘saviour’ to just a normal person. So Churchill and others obviously deliberately took the — correct — form to signify that even Hitler is just a man and not the god he wanted to be.
Chances are that the true background of this usage has since been forgotten, and simple Herr Hitler drifted into common use as a phrase — not unlike Helmut Schmidt always calling the same person Adolf Nazi. Ironically, it remaines correct and the old implications are no longer recognised even by Germans.