How does the user get the private/public key with HMAC based request signing? I need to implement a HMAC signing of requests and I have read this article which explains the basics of what it is and how to achieve on theory.
https://blog.andrewhoang.me/how-api-request-signing-works-and-how-to-implement-it-in-nodejs-2/
But I have no idea how the user initially gets their public/private key pair. Is it during login or during registration? Do they change? If yes how do you send them the new private key?
Each site, users and the server, generate their public and private keys and announce them, by sending the public keys. This can be executed during the registration process. The server should not generate the keys for the users, otherwise, the servers must be totally trusted and you have to securely send the private key, somehow. 

You can use the  Diffie-Hellman Key exchange protocol or the Elliptic-curve Diffie–Hellman to generate the keys to use in HMAC or any other process.

Due to the man in the middle attack, you may need  to apply the improved version; Station-to-Station protocol