The solution to this is to encrypt the cloud backup with a key derived from a password that the user remembers and can enter into a new phone. The password has to be strong because the cloud provider has the encrypted data and has unlimited time to do a brute force attack. Unfortunately strong passwords are hard to remember and users hate them.

But there is a trick to prevent brute forcing of a weak and easy to remember password like your four digit phone unlock PIN. The trick is to have a secure element chip in the datacenter, with storage encrypted by a private key that can't be extracted from the chip. The chip stores an encryption key that unlocks your backup, but it can't be extracted from the chip unless you present it with the right weak password. The chip's firmware rate limits and caps the number of attempts to unlock the backup, and if too many attempts are made it ultimately erases the key and your backup is permanently lost. So you're protected against brute forcing even with a weak four digit unlock code. If you know the unlock code from your old phone and enter it into your new phone, the secure element validates it and releases the key so you can restore the backup.

Obviously you have to trust the manufacturer of the secure element for this to work, but it's probably a good compromise for most users because losing your backups when your phone dies is quite bad. I know Google's Android backup uses this method and I believe iCloud does as well. It seems like Messenger supports this too but you have to choose your own PIN because Messenger doesn't have access to your main phone unlock code.