Practically speaking, you've described the Internet. On a basic level, every connection appears to a web server the same way: as an IP address with maybe some possibly-falsified identification tacked on. Unsurprisingly, there's been a lot of research into how to certifiably identify people on the Internet, and we can can use many similar methods in our hypothetical society.
Body Modification and Personal Style
For day-to-day, on-the-street identification, clothing and accessories as well as more permanent body modification such as hairstyles, piercings, tattoos, and scarification would all provide a means of identifying individuals. This is analogous to the screen names, email addresses, and whatnot that people use and reuse throughout the net. It wouldn't hold up in a court of law, but it's quick and simple as long as everyone's more-or-less buying into the system and playing along (e.g. not deliberately cribbing one another's styles).
Friend-of-a-Friend and Public Recognition
As a slightly more secure method of introduction, look for the personal connection. How do you know who someone else is? Either ask someone you trust, or ask a bunch of other people who would know.
Of course, if that doesn't resolve the issue, go to the next section to use more secure methods.
Secret Knowledge and Cryptographic Methods
For the most secure situations, you'd want to use some of the cryptographic techniques that have been developed to definitely identify oneself online. Think public-private keys and similar methods. I admit that this isn't my area of expertise, so I'll let others better-informed weigh in, but I can imagine a central public-key registry that is used to verify that the individual claiming to be Bob knows Bob's private passkey.