The cleanest approach for this would be a client server model as you guessed.
This simplifies client code a lot, as compared to database approach, but you need to setup and maintain a server.
You will anyways need a centralized entity (as a matchmaking service provider) if you want to let the user choose a random game. So I would suggest to go for setting up a server.
Following libraries might be helpful.
- Netty (low level but versatile)
- KryoNet (easy, high level features but limited (more than enough
for games))
- jWebSockets (Very good real time performance with long lived TCP
connections)
- Photon (Realtime, scalable, cloud, high performance but NOT
FREE)
There are many more... just search
Hope this helps.