And I'm not sure there's a good solution. The obvious approach, as you already know, is to separate headers into two groups: one group is "properly" handled, and the other group gets tossed into an "other" bucket of key/value string pairs. But it's going to be awfully tempting over time to have "proper" support for the most common non-RFC2616 headers, especially those which have widely-accepted standards of their own.
But that's a bit messy and much less than ideal, as you've also discovered. And I don't know of another way to approach the problem that still lets you have the stuff you want from the type system, and doesn't cut people off the minute they start using extension headers your library doesn't know about.
And that's without getting into all the completely stupid things it's technically legal to do in an HTTP header, and the even more stupid things that aren't legal but that people do anyway. My usual torture test of an HTTP library these days runs through things like non-ASCII content in header values (legal if properly encoded, and not everything in the wild properly encodes), looking to see how large a value a library will accept, whether it will let me throw newlines into headers, etc. etc.