How can I determine if a microcontroller is damaged?

If I was to fully test each MCU for its correct functionality, I would build a test board for each, with an adapter or socket to aid the easy change of the IC. Connect each IO pin to a visual output such as an LED, and program it with a simple firmware that will test each pin in turn. A further step would be to test the communication and other features depending on how thorough you want to be.

However if you simply want to quickly check the MCU is communicating properly with the programmer. I would use a programmer such as Pocket AVR Programmer, with a breakout board or adapter for each MCU. Then using the command line quickly test each MCU to see if it responds.

An example for the ATTiny2313 would be:

http://www.ladyada.net/make/usbtinyisp/avrdude.html

Program them with a non-optimized, easy to debug/observe code. If it doesn't act the way it should, but does on a known good chip, then you can assume the chips are damaged.