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.