Implement password recovery best practice
When I was in the Air Force the security rule we had was: When setting or resetting passwords, do not send the user id and the password in the same email. That way, if someone is intercepting emails snooping for passwords, he has to successfully intercept BOTH emails, and be able to connect them, to breach security.
I've seen a lot of sites that use the "go to this URL to reset your password". Maybe I'm missing something -- I don't claim to be a security expert -- but I don't see how that is any more secure than just inventing a new, temporary password and sending it. If a hacker intercepts the email, why can't he go to that link and see the new password as well as the legitimate user could? It looks to me like extra hassle for the user with no security gain.
By the way, congratulations on NOT using security questions. The logic of this device escapes me. Since the dawn of computer security we have been telling people, "DON'T make a password that is information about yourself that a hacker could discover or guess, like the name of your high school, or your favorite color. A hacker might be able to look up the name of your high school, or even if they don't know you or know anything about you, if you still live near where you went to school they might get it by tryinging local schools until they hit it. There are a small number of likely favorite colors so a hacker could guess that. Etc. Instead, a password should be a meaningless combination of letters, digits, and punctuation." But now we also tell them, "But! If you have a difficult time remembering that meaningless combination of letters, digits, and punctuation, no problem! Take some information about yourself that you can easily remember -- like the name of your high school, or your favorite color -- and you can use that as the answer to a 'security question', that is, as an alternative password."
Indeed, security questions make it even easier for the hacker than if you just chose a bad password to begin with. At least if you just used a piece of personal information for your password, a hacker wouldn't necessarily know what piece of personal information you used. Did you use the name of your dog? Your birth date? Your favorite ice cream flavor? He'd have to try all of them. But with security questions, we tell the hacker exactly what piece of personal information you used as a password!
Instead of using security questions, why don't we just say, "In case you forget your password, it is displayed on the bottom of the screen. If you're trying to hack in to someone else's account, you are absolutely forbidden from scrolling down." It would be only slightly less secure.
Lest you wonder, when sites ask me for the city where I was born or the manufacturer of my first car, I do not give an actual answer tot he question. I give a meaningless password.
</rant>
First off, do not store a plain-text copy of the user's password, or even an encrypted version. You want to only ever keep a hashed copy of the user's password.
As for recover solutions, I find that the recovery link to change the user's password is the best solution in my experience. It will probably be a bit more convenient for the user, while being largely the same from a security point of view as sending a new random password to be changed after next login. I'd still recommend having the recovery url expire after a reasonable short period of time, as well as only being usable a single time.
Hard to say what you should do, as pretty much any solution to this problem will weaken security. Unless maybe you want to investigate sending an SMS, callback verification, one-time password generators, or other such schemes that take password recovery to a different medium.
However, what you should not do:
Send the password - because after all, as has already been mentioned, you don't have it.
Generate a new temporary password - not only is this as insecure as sending the password, it also leads to the possibility of a denial of service attack. I can go to the site, pretend to be you, request a new password and then (if you haven't checked your email) you can't log in, don't know why and have to request a new new password ...
The token is probably the way to go. Receiving it notifies a forgotten password request, but doesn't take any action unless you confirm. You would also make it a one-time token with a relatively short expiry time to limit risk.
Of course, a lot depends on the application. Obviously protecting financial and other sensitive information is more critical than preventing your account being hacked on mytwitteringfacetube.com, because while it's inconvenient, if someone wants to steal someone's identity on a social network site, they can just open their own account and masquerade with stolen information anyway.