Can I use a HMAC for Replay Attack protection?
An old but excellent paper on this topic is Tuomas Aura's Strategies against Replay Attacks.  

The simplest version of the "Hashed Full Information" method would be to include the MAC of the previous message in the next message (you may also be able to use this as the nonce).  Then store the most recent MAC along with the session key and check new messages against that.  This would force serialization of messages within each session. (Assuming that is what you were thinking of when writing "use HMAC".)