When run cat says: "Hello, nothing to see here! Move along!"

Solution 1:

Well, so everything indicted in the chat session seems to indicate that your machine was hacked. Unfortunately we were unable to pinpoint the who, and most importantly, the how. Regardless, whoever did this seems to have become tired of the play and given up. After this, it was possible to solve the cat problem, with a sudo rm /usr/local/bin/cat2 (Attention, potentially dangerous command!)

You should now format your hard drive and reinstall Ubuntu from scratch. The problems you are facing in that front are, I think, content for another "Ask Ubuntu" question, where someone more knowledgeable than me will be able to help you.

Best of luck with your reinstall.