To have an FM receiver work on a phone, you do need an antenna, the wired headphones serve that purpose perfectly. An FM transmitter is easy to find; you can use the simple 'Jack-to-FM' adapters designed for car radios, or much better, a USB SDR (which can range from a few kHz to GHz).

Regarding the 'protocol for the waves,' you'll need to play with modulation. That’s the fun part. In technical literature, there are many well-defined modulations (like AFSK or FSK) with clear suggested applications for low-SNR environments.

As for Android support, I have no idea. I understand that in this thread, 'free' sounds like 'freedom,' but freedom has a cost. The freedom of communication requires investment: in hardware, software, and the time to learn the physics of the environment.