Users have to back up a 12-word mnemonic phrase, a la BIP39. We also email users an encrypted copy of their phrase (where their password is the key)

I think email is a reasonable place to do this since it's one of the few storage places people keep around across devices (sadly, other services with no centralization at all can't easily send SMTP). Could also consider a printable QR code I guess. I assume the Blockstack browser or whatever makes it easy to enter your clear text 12 word phrase or the encrypted one w/ the password when using a new device. I also assume that there is no way to revoke access by device (e.g. per-device keys but still same identity and some revocation list, I dunno). These are definitely tough problems.

Another decentralized app, https://keys.casa/, is solving a similar problem.