Yes, ideally, you run an IETF ZeroConf implementation (Avahi, Apple Bonjour, etc.) on each device, and each device responds to service discovery requests and hostname-to-IP-address resolution requests itself.
Avahi implements IETF ZeroConf networking (which Apple calls "Bonjour"). This is basically a cluster of 3 technologies:
- IPv4 link-local addressing (Microsoft calls this "APIPA"), where hosts can assign themselves 169.254.x.y/16 addresses.
- Multicast DNS (mDNS), where hosts can use multicasts to ask for each other's hostname-to-IP address mappings.
- DNS Service Discovery (DNS-SD), where hosts use mDNS to announce what services they offer, and to query other local hosts for what services the other hosts offer.
Devices running IETF ZeroConf implementations, including Avahi and Bonjour (OS X, iOS, and even Windows with Apple's "Bonjour for Windows" installed) can discover each other's services and resolve each other's hostnames to IP addresses.
It's possible to make one ZeroConf host act as a ZeroConf proxy for other devices that can't do it for themselves, but that usually takes a bit of setup, and the idea of having to set anything up goes against the whole meaning of "Zero Configuration Networking". The ideal is to have all the devices on your network, out of the box, already doing ZeroConf.