Introduce via a uuid represented as hex, psuedo-pronouncable syllables, or a barcode.
Every uuid maps deterministically to an abstract avatar which can't be changed. It can be canonically 64 or 128 bits, but allow the user to see a 32 or even 24 bit visualisation if they please. If identities have significant cost (such as needing to subscribe to a provider or to be embedded in your local social graph) the smaller should suffice even as a default.
Allow saving with whatever name you please to a list or using the target's name for themselves.
Allow sending a contact with metadata including optionally the nickname
Allow lists to be published, and whole lists to be saved as entries.
Don't hide the uuid ever because that's condescending and introduces many vectors for bad things. People learned what phone numbers were, trust them to learn what a UUID is if you stop shifting the sand under them for a minute and hiding what is actually going on at every opportunity.