Can I pass custom data in the HTTP header?

Its a bit unorthodox and I'm sure some purists would be upset at the idea (the headers should only be used for the transport of the message, and should not contain the semantics of the message).

Practically its doable, but you want to be sure all your clients can add these headers. If your clients are using tools to call the web methods rather than generating the HTTP requests themselves (which I'd hope is the case) then there's a real chance this is a problem.

Why is it so hard to add these additional overloads of the methods?

Yes it is allowed - but note that it may cut off the ability to use proxies and sometimes http aware firewalls (they tend to inspect and rewrite headers).