Do you understand that your server has been deeply compromised?

Do you understand that, if you've been rooted, you cannot trust the operating system anymore?

Do you understand that this may be why the quick fixes you've tried have had no effect? And even the sophisticated ones.

If you cannot trust this system to do what you tell it to, you cannot trust any of the quick fixes. They don't need gcc to upload C commands, just somewhere to write files and chmod. He doesn't need your compiler, he can use his own, and just upload the binary. All he needs is a way to set it executable.

If you deny him chmod, he can still just cp /bin/sh /path/to/my/executable ; cat my_binary_code > /path/to/my/executable. Perl, a C/C++ program, is neither more secure, nor less secure, than C/C++ itself. In any case it's not the language that grants things permissions to do things, it's the operating system itself.

Locking them to a specific language is not security. Denying them the permissions they need to do anything untoward in any language is security. There is no rubber chicken we can wave that will make your infestation go away. If you haven't been rooted, you might be able to hunt down the files with find /tmp/ and picking through them by hand. It is vital for finding and dealing with filenames that cannot be typed in the terminal, since you can refer to files by inode.

Check /proc/pid/ for the rogue processes in question. If they don't show at all, you've been rooted. If they do, /proc/pid/fd might reveal what files they're running from.

There might be a firewall rule to drop those outgoing ports, but how to do so depends on what your firewall is already and what your network setup is.

And if you have been rooted, then your OS itself, the thing which you're using to try and track down and fight this problem, is the thing that's been infected. Catch-22. Many of us have. This is how we know it's not as easy as you'd like. You know the saying, an ounce of prevention is worth a pound of cure?

You say you have no backups, too. This may be a good time to back up your customer data, but check it carefully when you restore.