1. Use the device's address book (phone numbers).
2. Use Facebook Connect (FB id).
3. Store the entire social graph on the server (custom identifiers).
I think #3 is what every messenger that offers non-phone identifiers does (Snapchat, Twitter, Telegram, Wire, Viber, etc).
The reason is simple: if someone does manage to create a social network by slowly discovering a bunch of usernames from their friends, but then they reinstall the app or get a new phone, it would be pretty unusable if that entire social graph was just... gone. It's bad enough to have to create this social graph from scratch, but to do it every time you reinstall, lose your phone, or get a new device?
The consequence is that many people advocating for this feature (or using other messengers because of it) probably don't understand what it is that they're really advocating for or getting themselves into.
Right now Signal is much more "private" than any other messenger, if you measure that by how much Signal knows about you (timestamp of account creation is the only thing iirc). By supporting a custom identifier, they would have to store your entire social graph, like other less private messengers.
On iPhone, after a hardware upgrade w/ restore, Threema offers to restore your client side graph from a client side backup.
Use the phone number just to prevent spam (though it can't prevent one user having multiple accounts using the same phone number).
This will serve two use cases:
1. People who need simple private IM like WhatsApp can continue using it without asking for A or without giving it any heed.
2. Or you go for A and you are communicating w/o any real world identity attached to your messages.