Sure, but you also just... don't have to do that. None of that is necessary fore core functionality of a messaging service, IF you stipulate that both devices must be online at the same time to ping each other.
The only thing you need is some very basic addressing service so they can find each other, and there are entirely P2P solutions for this that already exist and work without issue. See: bittorrent.
The ONLY drawback of having no server, fundamentally, is that the two devices need synchronicity. If they both aren't online at once, messages won't get delivered. Which is not a big deal for a modern smartphone given that most of them are online close to all of the time.