You're right. Prostitution is the wrong analogy entirely. This is much worse.
Playing music in public for free is fine under certain circumstances. If you've negotiated a deal whereby you only get paid if the venue gets a certain amount of paying customers, or they sell a certain amount of food or drink, then you could end up not making any money. Or, if the venue isn't charging anyone to enter, and isn't making any money either, then you could perform for free I guess. Or, I could see performing for free if you have an agreement that the club will hire you at a fair wage in the future if you draw an audience or appeal to whatever whim they stipulate.
Lastly, I could see performing for free in a venue that has some sort of recording setup that would allow you to record your show (audio and/or video) for the purpose of putting together promotional material.
But to perform for free, when the the venue is charging for admission or making a profit on food or drink, is doing a disservice to everyone, especially other bands who refuse to sink to your level.
Let's face it, if no one is willing to pay for what you're doing, you probably shouldn't be performing in public. Just put a video up on YouTube and see if that generates any interest. Otherwise, you're just performing to stroke your own egos.
If you're convinced that a performance will result in new fans for your band, rent a hall and put on a show. Then you can charge admission or not.