The .txt icon changed to a Unix executable icon as soon as I removed the .txt; did I still have to chmod?
no, the original chmod you did still holds true.
(I don't follow So if you type the full path ~/Desktop/cc.txt then it will execute. Isn't that what I did when it wouldn't execute?)
I don't see anywhere where you actually tried to execute the cc command.
chmod only sets the x bits... it doesn't run the file.