The flow you're describing in your "possible solution" is basically identical to how Signal works now: you install Signal on a new device, approve it with your existing device, and are done. Anything involving the word "blockchain" here is fundamentally not going to work. It sounds like you want CONIKS, but there are some really substantial barriers to deploying that for marginal gains (and some clear losses).