You'll also want to implement some defense against short-term replay attacks (i.e. before the token expires).
You could include a sequence number in the token, but this, of course, involves a database write, which is what you were trying to avoid in the first place.
A better approach would be to store in the database the time that the user's password was last changed, and refuse to honor any reset tokens that are timestamped prior to that time.
Beter yet, mix in a random data field from the user record into the reset link (have it signed with HMAC), and regenerate the random each time reset it done. This way no reset link can be used twice, and no db writes are done when reset link is created.
You could include a sequence number in the token, but this, of course, involves a database write, which is what you were trying to avoid in the first place.
A better approach would be to store in the database the time that the user's password was last changed, and refuse to honor any reset tokens that are timestamped prior to that time.