How can I get a unique ID for all my Arduino boards?
There are a number of techniques you could use here to get a unique ID.


FTDI chips have a unique serial number programmed onto them. This can only be accessed from the PC side of the connection as far as I am aware.
Some of the chips with built in USB (e.g. ATmega8U2/16U2/32U2) have a unique ID in the signature data, normally used for USB. Can easily be accessed from both sides of the connection. This includes the ATmega16U2 that is used as the USB->Serial bridge Arduino Uno R3.
Some of the chips with built in USB but no unique ID in the signature will still have a unique ID programmed into the USB stack (e.g. LUFA) used for the bootloader or DFU (Device Firmware Upgrade).
There are many chips with globally unique serial IDs in them e.g. the Microchip 11AA02E48, all of the Dallas 1-Wire sensors (including the common DS18B20 temperature sensor), and other serial EEPROMS. I've used these in production hardware that must have a unique MAC address.
You could modify the standard Optiboot bootloader (or whichever boat loader you use) so that it can hold and respond with a unique ID. 


The problem with these is that there is no option except 5 that will work across all boards.

If your solution is going to be a generic one, I would suggest that using a USB ID is not the way forwards. I have ~30 Arduino-based boards, and only 5 of them have built in USB hardware. All the rest of them need an external FTDI cable to be programmed. This means they would all have the same ID.