First, a few things:
- There is no shared secret in Thomas Pornins answer to the linked question. The server uses a secret only it knows to compute the HMAC. The client then gets that HMAC, and sends it to the server on every reqeust as an authentication token. The server can check it by recalculating it with the servers secret. Note that the client never calculates a HMAC.
- Rather than implementing this yourself, you probably want to go with an existing solution, like JWT.
But still, the HMAC or JWT or whatever needs to be kept safe client side. Personally, I'd put it in local storage but a cookie could also work. You rule these out as they are vulnerable to "leaks". It might be true that malware running as root, or someone with physical access, could steal these. That's a risk. But here's the thing: All login system, from old fashioned session IDs to modern JWTs, works by letting the client store a secret. If you can't accept that risk, you can't have login, and you'll need to have the user retype the password on every request. (But who knows, malware that can read local storage could potentially read keystrokes as well...)
Not sure exactly what you mean with using a new secret for every round trip, but it couldn't solve the above dilemma. At the first request, the client authenticates itself with a password and gets a secret it can use for future authentication in return. At the next request, the client has to authenticate itself again. Either, it has saved the secret and can use that. Or it has not, and then the user has to retype the password.