1. Supposing all the more-convenient ways have broken down (no keyboard, no mouse, etc.)
2. The OS displays a random 15-60 second countdown telling the user when to unplug the device if they trust it
3. The OS displays a second (random) countdown telling the user when to reconnect the device if they trust it.
4. If both steps succeed to a reasonable level of accuracy (some fudge-factor for humans and for slow-powering-up devices) the OS will begin trusting the HID device and installing drivers etc.
This requires no additional hardware except for a monitor, and evil devices cannot reliably brute-force it without taking a lot of time and being very obvious and obnoxious about it.
It would require that all these devices have at least some basic functionality with only some standard drivers. I don't know how true that is right now.
"The following USB device has requested direct control over your mouse and keyboard inputs. Do you want to grant it access?"
"Note: If you are unable to interact with your computer, please wait X seconds for emergency instructions on how to enable this device."
You can't make anything totally idiot-proof, but a lot of people will be surprised/scared when a very unusual and seldom-seen dialog pops up when they plug in a particular misbehaving memory stick.
Not great, but certainly a lot better than a 100% certainty of fooling the PC.
Plus, 99% of the time the user is not plugging in a HID device, so the "unrecognized input device" dialog can be made ominous enough that users will realize something is very strange about that one USB stick.
You just have a timed dialog with allow/block options that defaults to allow the new HID after the timeout.
Unfortunately without going back to Windows 95-esk "please restart to install this keyboard" world, I cannot see how you fix this. Even blackholing some input from the HID is only at best a temp' solution (as they'd just add longer and longer sleeps before fake HID input was generated).
I guess you could redirect all HID input to a certain context (like a Virtual Desktop e.g. UAC prompt) until the user accepts it. However realistically most users would ignore this warning and just click "install" without reading it or understanding the implications.