Using HMAC-SHA1 for API authentication - how to store the client password securely?

This is the downside of symmetric-key challenge-response style authentication - you don't put the secret on the wire, but you have to store the secret at both ends. (HMACs are symmetric key systems).

Note though that it's not a password - it's a shared secret. There's a fundamental difference here - a password is generally chosen by the user, whereas a shared secret is generated randomly and provided to the user (they're often called "API keys", in this context).

Storing passwords in a reversible format is bad, because if your database is compromised, then the attackers have obtained passwords that might (and probably have been) used elsewhere. Storing a shared secret, on the other hand, is not such a problem - the secret it's specific to your service, so all the attackers have gained is the ability to log in to your service.

On the other hand, it is possible to have an asymmetric system that doesn't have to store a secret at the server side. The basic idea is that the server knows the client's public key and current message sequence number. When sending an API request, the client increments the message sequence number and calculates a signature over the sequence number and the API request parameters, which the server can verify using the public key. The server rejects a message if it contains an old message sequence number, to prevent replay attacks.

Ideally after the user logs in you give them a Cryptographic Nonce which is used as the HMAC secret key K for the life of that session. This is a secure approach, but its not RESTful, because REST is stateless. This idea of an message authentication code issued per login is technically a form of state.

Encrypting passwords and storing them in the database is a violation of CWE-257.

I am not sure if i am missing something here but one option is to use hashed password as symmetric key.