My usual way of approaching this is to encrypt the password with the sha512_base64 method from Digest::SHA. I then generate a random 40 character string to salt the password. The random string gets changed when the user changes their password. I split the 64-character encoded password into two parts and insert a hash of the salt. I split the encoded password a different place for each site I write.

I reckon that's pretty unbreakable without access to the codebase.

But, the difficulty isn't encoding the passwords or storing passwords and possibly salts.

As you rightly point out, the biggest difficulty is that we can't just send out encoded passwords. Once encoded, users need a means to select a new password, and that means a whole new workflow needs to be created. It's simple enough to do but there is quite a bit of work. Another issue is that it would be difficult to properly test without a test server but certainly not impossible.