Hard to visualise how you're going to go about building and dispatching these things or what sort of interfaces you have available, but I assume you're going to install a sketch on them before shipping. Is there any way for the sketch to receive a serial number via SPI, serial or whatever other interface you have available and write that to EEPROM? The aim would be to do this at the same time you print the corresponding label, and perhaps do both of those at the same time you upload the sketch if that's something you're doing yourself. In other words physically plug the device in, push the button to upload the sketch and serial number, that causes your labels to be printed, Arduino and labels go onward to packaging.