The client and server establish a secure connection using https, authenticating via regular ID and password. The server provides the client with a regular session ID, and a new session_signature_key which the client will hold in memory and never send back to the server.
Each server response includes an unsigned random 64 bit challenge with each request between client and server. The client will sign this value with its session_signature_key, and return this signature in its next request. The server barks if the signature does not match expected the challenge response from the user.
The server would obviously have to keep the user / session_sig_key / last challenge map in mem, but it seems easy enough.
[1] parallel requests should be doable as well, but I'm still thinking about it.