There is a free way. There is a legal way. There is not a free, legal way.
Free way
Get a DynDNS account, and a Raspberry Pi. Host the exchange on your home internet connection.
I can't think of any reason why someone would trust their money to my_exchange.dyndns.biz, but I suppose you could do this.
Legal way
Money service businesses are generally regulated state-by-state, so it's difficult to give you general advice. I would suggest that you find a lawyer that practices law in that state and who specializes in banking law; they can tell you what you need to comply with. If you do not know a lawyer like this, I suggest going to a lawyer you do know and asking for a recommendation.
When are the legalities surrounding exchanges like coinffeine, where two anonymous users exchange and coinffeine acts as the intermediary?
Those two users are breaking the law. Operating an unlicensed money service business is against the law, and people have been arrested for exchanging Bitcoins. (Also, if you operate an unlicensed MSB, you're automatically also committing a federal crime.)
Whether Coinffeine is also breaking the law is a very interesting question that I am totally unqualified to answer.