I think another solution would be to insert and compile the source of a different compiler, hopefully a rare one like TCC, or even a C interpreter of some sort. The evil compiler can't be programmed to recognize all conceivable C compilers; there must be a small finite list it understands. (This was probably a difficult option back then.)
Depending on how advanced the evil compiler is... Plan A would be to use it to compile TCC, then TCC to compile the original compiler. If the evil compiler inserts into every binary the generic command sequence "search for files that look like the original compiler and evil-ify them", then Plan B is to use evil to compile TCC, then use the resulting slightly-evil-TCC to compile TCC, then use the resulting clean TCC to compile the original.
If someone has also modified the kernel such that anytime someone uses the syscall "chmod" to mark a file as executable, it'll add evil instructions to that file... Well, perhaps you could recompile the kernel, but it'd be easy for evil instructions to cover that too... finding a new independent kernel source that runs on your machine is probably pretty hard... it'd also kind of interfere with downloading good binaries onto the machine, if the process was "download to a file, then chmod", though if it was "chmod, then write to the file", the evil kernel would have to be clever enough to make it instead append to after the evil instructions; you also could attach a disk and mount it and run executables already on it, and that would be pretty complicated for the evil code to transparently handle (of course, it could just refuse to run such things, but there are lots of things it could refuse to do).
