how to authenticate

So now I'm at the point where I need to work on the authentication part for the stats server code, and I noticed that my plan to use http digest authentication doesn't work as that requires to store the plaintext password of clients on the server which I'd like to avoid (generally one should only store a hash of the passwords in the authentication backend).
Before going into alternatives let me list a few requirements I have for them:
- don't require the real password in the auth backend
- don't transmit the real password unsecured over the network
- must work with only http headers, don't touch the body in any way
- must be easily scriptable
- preemptive authorization (e.g. send the auth data with the first request)
- should work within a webbrowser
So, what options do I have now? Well, I can't see a single alternative that fits all requirements (if you know one let me know), the closest is http basic auth, but I really don't want to send the password over network as almost-plaintext. This lead me to the idea of extending it with gpg-encrypting the password, but that's not transparent when you use the browser (not that important for the current use case) and more importantly gpg adds about 600 bytes of protocol overhead for encrypted data (without using --armor), with the base64 encoding required for http that's almost one kilobyte just for a password that originally only had a few bytes.
So, right now I have to select between a rather hackish, inefficient and untested but secure solution and a well-tested, relatively efficient and well-specified but insecure one. What would people prefer here?
Or does anyone know another solution to the problem that satisfies the above requirements? (the first four are hard requirements, the other two I could work around)