Well, bar'ing a "secure way" to do this, I'd say to mail them a new, strong password... as long as you have "verified" their email address (I think AO does this sort of thing, too).
1. User chooses new id
2. If UserID exists, rinse and repeat (though this is a brute-forceable user list problem)
3. Mail them a strong password / link to verify email
4. They login and set their password
...if they forget the password, start at step # 3, first WARNING them you were going to mail it and, as others have said, don't include the userid.
In any case, if their mail bounces, lock the account until verification can be (re)established.
For "advanced" users, you can do PGP (using their KeyID on a public key server). If they lose that key, though... things get more interesting.
Hold their firstborn child as proof and if they need it reset ask the kid which one of these people are your mommy or daddy...can't go wrong there....
sorry butt end of 12 hour night shift where 1:25 is actually 6:30 am
Combination of Unleashed and str34m3r. Have them choose from a list of questions going in, then give their answer. If they forget they have to choose the same question and give the same answer. However, I'd just take them to the new (or present) pwd on a secure page instead of emailing it to them. Reason: a person can secure their 'puter with a bios pwd that most friends can't reset to use the machine if they did have access, but their 'friends' can pirate their email pwd pretty easy. Just MHO.