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.