Set a flag to inactivate their account (You'll need to make adjustments to the login script itself), and then create a temporary encrypted password, and send that as part of a link to the user. When they click the link, it sends them to a page where they enter their email address and submit it. When they do that, it verifies that email address along with that variable (encrypted password) you sent in the link, and prompts the user to set their own password. Once they do that, then you can activate their account by resetting that flag you set from the start.
This accomplishes several things.
1) Verifies the right user's email got the email.
2) Ensures the user sets their own password to hopefully have a better chance to remember it.
3) Ensures you have no liability to their password or account by forcing them to set their own password. (That way, if something happens in their account, they can't claim that it's your fault, assuming you take the necessary precautions against compromising their password)
4) Ensures their account is inactive and can't be loged into until their account was properly verified, and the password was set.