You can do what apple does for disk encryption:

* Encrypt the data with a key (let the user print it out if you like)

* Encrypt the key with the password of the user (or multiple users!)

* Store the encrypted-encrypted-key on your server.

If a user wants to change their password, their old password decrypts the key, and the new password re-encrypts the key.