The problem is the social graph. You need to know the ID of all your contacts at some point, right? Either that's stored on the server (e.g. your Facebook friends), but then the server has access to it, or it's stored locally in your app, but if you lose your phone then you lose your graph. Signal has been working on a way to store your graph securely on their servers, but it's hard, and not there yet.
The great point about your contact list is that it is decentralised, and it exists already (so you don't have to exchange an ID with all your friends manually).
It feels like everyone keeps repeating the same dialog tree that 'but thou must store their contacts list' and I don't see why.
Solution? Store your contacts list on your device. Back it up with your offline chat backups (android does external chat backups now, IOS should be enabled plus give em icloud backups to boot).
with a new signal app on a new phone, you restore your chat backups and poof your contacts list gets loaded back. your new signal instance reconnects with the other clients and poof, Signal's excuse for using phone numbers and storing your contacts list on their servers is demolished.
It seems so simple to me, but I feel like I'm failing to understand something about why this is so hard.
Because you forget that you need to build your contact list (if you don't use the phone numbers), which for 99% of users (including me) is a major pain.
Then your backup idea works, but kind of sucks in terms of UX (at least in Signal's point of view), and therefore they decided to go with phone number first, and work on going towards usernames later.
Don't worry, you haven't invented anything. It's just that your idea is not at the level of UX provided by WhatsApp/Signal, and the solution is more complex than you think.
The great point about your contact list is that it is decentralised, and it exists already (so you don't have to exchange an ID with all your friends manually).