How would I create "Omegle"-like random chat with gevent?
If I've understood you right, you just need to link the second person with someone connected before. Think it's simple.
The greenlet working with a person who comes first  ('the first greenlet') just register somewhere it's inbound and outbound queues. The greenlet working with the second person gets this queues, unregister them and use for chat messages exchange.
The next person's greenlet finds out that there is no registered in/out queues, registers its own and waits for the fourth. An so on.
Is it what you need?
I have searched tutorials and documentation for gevent, but seems that there isn't lots of it.
I have coded Python for several years, also I can code PHP + JavaScript + jQuery.
So, how would I create Omeglish chat, where one random person connects and then waits for another one to connect? I have understood that Omegle uses gevent, but my site would have to hold 200 - 1000 people simultaneously.
Besides the server side, there should be fully functional client side too and I think it should be created with jQuery/JavaScript.
I would need little help with the coding part. I can code Python well, but I have no idea how I would make that kind of chat system nor what would be the best Python library for it.
The library doesn't have to be gevent but I have heard that it's very good for stuff like this.
Thanks.