1. Each participant starts a Tor Hidden Service.
This would require all nodes to run Tor! Why not do the CoinJoin negotiation over BTC's network protocol, which the nodes participate in anyway? This way, those who use BTC through Tor also do the negotiation through Tor, but no one has to.
There is little benefit to negotiation over the Bitcoin network protocol for traditional CoinJoin's besides eliminating the need for an additional networking layer.
On the downside, adding additional messages to the network protocol is likely an irksome process, and is not very flexible. A separate network may be rapidly iterated upon, and other shared transactions other that traditional CoinJoins may be added.
In regards to Tor, for Java there exists the Orchid library, which allows Tor to be easily integrated within Java applications. The main benefit of using Tor Hidden Services (to me at least, if I am understanding things correctly) is not really anonymity, but rather NAT traversal. Without Tor, you have to keep a port open to allow users to connect to you node and perform a decentralized CoinJoin. Tor hidden services connect to Tor Relays, and therefore do not require any ports to be open. As long as the NAT/firewall allows outgoing Tor connections, everything works out.
EDIT:
I forgot to mention, a downside of using Tor is that TomP2P and all other Java DHT libraries that I know of require ports to be open to ensure the integrity of DHT (if no nodes are hosting the DHT information, what's the point?). As such, in order to make the DHT robust the code would have to be extended to facilitate Tor Hidden services. This doesn't even address the fact that using a DHT to facilitate CoinJoining between number of users
n>2 is a real pain.
Hence, decentralizing peer discovery is a job for another
day week month.