I have done this before by doing and md5 on the concatenated record id and email address. You could throw in a few extra characters or fields if you want. Then when the user clicks the link you just run the same select again to see if you get a match.
// generate the key
select md5(concat(id,email,'Some custom text')) as `verification_key` from ...
// verify the user
select * from user where '$verifikation_key' = md5(concat(id,email,'Some custom text'));
Then you can update the user record to mark as verified.