I got an idea, maybe it's stupid, maybe not - surely it contains "overkill" part but the differences in prices between microcontrollers being so small it may pay better than entering the code "by hand" into each chip separately... (or may not, for that matter. YMMW)

Let the microcontroller generate an ID that is "almost granted" to be unique - a big random number. You just need a source of noise and some PROM writable at runtime.
For example: I was recently using ADuC812. It has temperature sensor built in. Upon first power-up after uploading the program, set the ADC to 12bit mode, concatenate lowest bits of some 200 readouts of the temp sensor (and if it's not "noisy" enough for you, attach some noisy diode or something to ADC input) and write it in the (on-chip) RAM, treating them as the ID and set a flag there so the procedure won't be launched ever again. It's practically granted the set of bits will be unique in each device despite the fact they were all manufactured the same and uploaded with identical software.