You can either use a timestamp (that is included in the HMAC calculation to ensure it isn't changed) to allow a replay-window (this is what AWS does) or you can utilize a NONCE value retrieved from the server before hand and recorded as "played" once it is used so no other requests can ever be sent using that nonce.
Using a NONCE has some advantages and some disadvantages. There's no need to retrieve the nonce from the server, the client can generate any random value and include it in the signature. However, one of the beautiful properties of HMACs is that the server you're talking to does not need any stored information other than the shared secret to authenticate the request. That makes HMAC-Authentication feasible over a cluster of servers that share no storage if the secret is fixed. Using a NONCE requires that the servers share a storage that updates pretty much immediately, so they all need access to the same datastore that must have practically no replication delay. Otherwise an attacker could still replay the request, just against a different server.
