Where do you even get a trusted copy of the putty binary?

You download it from an unencryped, unsigned website, and there are GPG signatures available, but you can download the keys from the same unencryped, unsigned website.

A MitM attacker could easily manipulate the executables, sign them with his own keys, and do a MitM attack on the key page too.

This is not mere paranoia; we know now that the NSA has infrastructure to do such attacks fully automated and at scale.