I will answer your question in two parts:
The communication channel should be encrypted with RSA. How can I do that?
RSA is really slow to encrypt whole messages. The usual way this is done is to encrypt the message with a symmetric cipher like AES, then encrypt the symmetric key using the recipient's RSA public key.
Having said that, there are a lot of small details to get right, so I would advise you to use a pre-built implementation. In fact, just use SSL/TLS, use-cases like yours are exactly what it's made for.
OpenSSL in the most common TLS implementation, it's easy to use and will take care of all the crypto for you. Googling something like "introduction to openssl programming" should get you started.
EDIT: As @Volker pointed out in comments, many common instant messenger clients like Pidgin and Kopete use the library Off-the-Record Messaging which is an encryption protocol specifically designed for instant messengers. OTR uses PGP as the underlying encryption system. There is an OTR library for C available here, and a Java library here.
Now for the second part of your question:
Generate keypairs on every client and when a client tries to communicate, ask for public key? It is this safe?
Let the SSL/TLS handshake take care of all this. It uses a key-exchange protocol called Diffie-Hellman which solves the key-exchange problem quite nicely.
One thing you will want to think about is whether you need strong authentication, ie whether or not you're worried about people impersonating other users. If so, you'll need to get everybody's public keys made into certificates that ties each public key to a specific person. This is a much more complicated setup that will require some sort of Public Key Infrastructure - either you'll have to setup a Certificate Authority server (you can do it with
OpenSSL), or have a web-of-trust system like PGP does. If you do decide to go this route, you can find info on Google, on this exchange, or you can post new question(s) about setting up a PKI for your chat network.