A nonce when implemented correctly doesn't expose the client to replay attacks at all unless I'm missing something here. When requests come in, store the nonce + timestamp and ensure that requests with the same nonce + timestamp are only ever executed once.
