Problem with the random generator is that it is not so random at all, it is an algorithm and unless every sketch has an unique seed you will get the same signature for every board.
Furthermore if your boards have used the EEPROM before (or in a factory test who knows) your code will probably not write your signature, so you need an erasor sketch that writes 0xFF to EEPROM first otherwise previous values could be identical ... AVRdude can also do that.
It is quite hard to make this process automatic AND robust (failproof). I think I would use some makefile with AVRdude to write the signature to EEPROM after uploading the sketch, and that makefile would increment the EEPROM file every time called. It can keep track of the numbers applied on which day etc.
Or let some SED command change a signature in the source to some sequence number.
How many boards do you intend to label this way?
Rob