I strongly disagree with Chris S's claim that all files/directories should be owned by root. There is a reason for the Unix permissions system.
There are two basic ways to run Apache/PHP. One is to run it as the www-data user, and have the files owned by a non-root username. Apache runs as a low-privilege account and must be granted access to particular directories/files in order to write to them. This is why Joomla has the ftp layer, to compensate for this. However, in a shared server environment, the fact that all files need to be world readable makes config files for other sites on that machine easily read.
The other way is to run Apache with PHP running suPHP, which is what CPanel prefers. In this case, Apache runs as a low privilege user, but, all PHP requests are handed to a script that changes the ownership to the username that owns the files. While you can now use Unix permissions to prevent other rogue scripts on the machine to browse your directories, any compromised PHP script is able to be run as your username and as a consequence, modify/deface any of the files owned by your username.
Since you're not well versed in server security, finding well hidden rootkits, etc on the machine would not be a fun task. First, you'd have to know whether the kernel was exploitable (unless you're running a very recent kernel, the answer here is yes), and whether anything had been affected. This particular hack usually occurs through a compromised FTP account at which point they are able to execute scripts. Since you found that code, it also suggests that the 'hacker' using it wasn't very sophisticated. There are many ways that he could have hidden that code and prevented your logs from seeing what he was doing.
mojah is correct. Once they get in, they try to run a script from /dev/shm/.something or /tmp that connects to their IRC network, or, acts as a takeover bot on undernet or another competing network. You'll likely find one or two scripts running, perhaps a cron entry to restart it, and, other remote shells hidden throughout your Joomla installation. Look for files in the /uploads or /images directory named similar to existing files. i.e. img_1034.jpg.php. They will usually hide their irc bot in multiple places that aren't web accessible so that you won't stumble across them when you log in, but, will have stashed their remote shells in places so that they can get back in and rerun their script and have it reconnect to their network.
In any case, the task you're faced with is somewhat tricky. You've got a site that you need to stay online, you lack some of the experience with these situations, and, you just want your site to work.
Take a dump of your database through Joomla's export function, make sure it is a complete dump. Create a second site and import the dump to verify it. Once you are sure you have a good, importable dump, make a backup of the site. Delete all files, reinstall Joomla, basic installation, use the existing MySQL connection information - it might believe you are upgrading, in which case allow it to upgrade. If you are on a VPS somewhere, perhaps have them hand you a fresh image and reinstall.
If you're running a default configuration of Apache on Ubuntu (or have used the default config as a blind template for other virtualhost directives) you'll likely find that you have a ScriptAlias directive mapping /cgi-bin/ (relative to the apache document root) to the filesystem location of /usr/lib/cgi-bin/ - so what they're actually trying to load is http://your.host.name/cgi-bin/php4.
If you're not using your cgi-bin for anything, you're unlikely to lose anything you care about by commenting out the sections relating to it (and the more defined to your needs your configuration is, the smaller any potential attack surface).
You'll find the relevant directives for the default site in /etc/apache2/sites-available/000-default, if memory serves.
Best Answer
The error output you're seeing is typically related to the configuration you see here:
http://wiki.apache.org/httpd/DirectoryAsScript
In this particular case, I don't think you have anything to worry about it - it looks like you have a directory aliased in the config, and the IP you provided is actually the MSN/Bing crawler, presumably crawling your site, and eventually hitting that aliased directory (worst case, you can robots.txt it out of that directory to prevent future errors).