You can do it statelessly by just adding a timestamp, i.e. msg||timestamp||nonce

Clients can reject timestamps from the future outright, and for the rest, apply a decay function based on age, prior to comparison.