Is there really no supported model for this scenario? Surely the point of an iCloud backup is that you can restore from the cloud rather than do a local hack to try to regain access to locked keychain db.

What happens if you just set up the device as a new machine and login to your iCloud like normal?

there are some different options depending on settings - apple will encrypt to an internally (apple held) key that your iCloud login will unlock under most circumstances. This can be turned off by consumers, and I would expect by IT departments at well.