It might be a root kit, actually. A root kit takes over as a "god" user (the name for Linux super user is root, hence the name). They can control what is and is not executed. And those are really easy to deal with.
For the record, a Trojan Horse is malware that looks like another program that you execute by mistake.
A virus is malicious code that is executed and usually runs hidden and does not self propagate. Botnets are a common use of a virus and are usually installed using a security hole in another program (Adobe is the worst offender).
A worm is like a virus but self propagates.
Spyware tracks information. The most dangerous form is a key logger which can snatch passwords.
Addware is malicious code that causes popups and tries to bombards you with adds.
OK, those are out of the way, how do we fix this? Well the really bad ones, like what you have, will control EVERYTHING when you boot. So, what you do is NOT boot into that OS. Idealy you want to boot something that isn't writable, like a live Linux CD. See the link for the video below. This fairly attractive Linux nerd will walk you through the process.
As for AV, I use AVG on Windows and I haven't been hit with a virus since. As far as free goes, it's statistically the best, and very close to the paid Norton and McAfee (which has UVSCAN, the best AV for Linux, actually).
As for my credentials, let's just say Uncle Sam pays me to know this stuff (DoD contractor spending my days working with that penguin-loving OS, Linux).