nonce is ok as long as for your application it is ok to expose the client to playback attack only for a limited time. I would go for a pre-request protocol where you perform a request to get a request-seed, and then use it in the next request (and the server will remove it when already used).

Another thing that makes sense is to use a nonce plus adding the IP address in the string to sign, with server side verification that the IP matches. So at least the playback attack needs to be performed in near time with the same IP as the originating client, that is considerably harder for the attacker to do.