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.
The option to record the keys yourself is also described in the whitepaper:
"If the user decided to accept a cryptographically random security code, instead of specifying their own or using a four-digit value, no escrow record is necessary. Instead, the iCloud Security Code is used to wrap the random key directly. "
As I said, I can't actually find this option in my iOS settings. Maybe you have to disable Keychain first?
I'm no expert but this is my recollection.
In the scenario where you have 2 devices, one is iOS 9/10 and have migrated from 2SV to 2FA, the other is iOS 6/7/8, you can still access the recovery menus on the iOS 8 device, but it does weird things to the keychain if you mess about with it.
TL;DR: Keychain recovery relies on a cluster of hardware security modules to enforce the recovery policy. After 10 tries to guess your PIN, the HSM will destroy the keys. Apple support gates all but the first few of these tries. The paper also implies that you can use a high entropy recovery secret as an alternative, though I can't figure out how you would enable that.
This seems like a pretty reasonable point in design space to me. Of course, you are relying on Apple's trustworthiness and competence to implement this design. But that is true without recovery, since the client software is also implemented by Apple.