Let's say that I want to build a Dapp such that users can exchange messages between each other. I guess you can consider it a chat Dapp. Is there any way for the two users to find the "address" of each other on the blockchain and then start communicating without using any transaction or gas?
Theoretically, that's exactly the usecase for whisper.
For an example with addressing/encrypting via public key, see Looking for a working Whisper example
Practically, I am not sure how performant whisper is in it's current state. Not all nodes have whisper enabled. I am also not sure why nodes should spend resources on relying whisper messages. There is no direct benefit to them.