As I speculated elsewhere in this thread, I think they're going to do it with multiple recovery keys ostensibly written down by the user and never transferred directly to Apple, which each then redundantly encrypt all user data before transmitting respective copies to iCloud.
That would pull it off, and it basically just shifts the trusted device redundancy problem to a trusted key redundancy problem. The only remaining usability obstacle is to make sure the user has safely recorded all recovery keys.