Where should I add the unique identifier cookie code?
I think hook_boot() would be the best place for your code:

This hook is run at the beginning of the page request. It is typically used to set up global parameters which are needed later in the request.
Only use this hook if your code must run even for cached page views.This hook is called before modules or most include files are loaded into memory. It happens while Drupal is still in bootstrap mode.

(emphasis mine)