I've been reverse-engineering old microprocessors lately (e.g. Z-80), and I've been thinking about this question. For chips of that era, you can actually look at the silicon, examine what it does, and be pretty confident that there's no back door. (Although interestingly the Z-80 is said to have a few "traps" to prevent copying, where due to silicon doping tricks the circuit doesn't do what it looks like visually. But scanning capacitance microscopy would catch this.)

But for a modern microprocessor, it's impractical to reverse-engineer the chip at this level. One solution would be the manufacturer could publish the full plans and circuitry for the chip, which would make it easier to see if everything looks okay in the circuit, and then you could verify that what's on the chip matches the plans. For instance, if Intel published the circuitry for their digital random number generator, you could look at the circuitry, look at the chip, and be pretty confident that everything is okay. (Note that this could be published without being open-sourced. In a perfect world, patents would include all this information.)

The problem is for chips that have microcode that can be updated, knowing the chip itself is "correct" doesn't help you, since the microcode could be malicious. Even if the random number generator is valid, the microcode could modify the values before you get them. My conclusion is that even if your chip is 100% validated, it doesn't help you at all if you don't know what's in the microcode.

(This all depends on what kind of attack is being put into the chip, of course. I wouldn't notice any side-channel attacks built into the Z-80 such as timing-based attacks or power consumption. You could probably sneak in something super-obscure like the carry flag not getting cleared in some corner case and make it non-obvious, but that would be pretty hard to exploit.)

So, basically, design your own chip on paper (because you can't trust the CAD tools or the compiler that made the CAD tools), build your own fab and make your chip at home, build your own computer, write your own compiler, write your own operating system... Yeah, this'll be good.

Similarly, how do you know your compiler didn't add a backdoor to your software? Even if you compiled your own compiler, you don't know if the software you used for that is safe. Unless you trust your hardware and you bootstrapped your compiler, I don't think you can truly trust software.

One option (if you have a trusted FPGA) is to run something from opencores.org, where you can verify the code.

But more generally, yes there is an issue of having an initial base system which can be trusted to some degree.

Some strong solvent and a microscope? =)