After trying various hooks to try to set the cookie before the theme loaded it's header.php file (none of the hooks worked, even those very early in the 'load cycle'), I figure that I might temporarily disable the error so that the cookie can be set. I based my answer on this question.
Now, I realize that this is not a standard way of doing it, and probably not recommended, but my justification is that if a theme is not doing things 'normally' or 'correct', and therefore causing the 'headers already sent' error message to display on the screen, then quickly bypassing that error display (and then restoring whatever error trapping settings are in place) is a solution that will work in my situation.
It appears from my testing that even if 'headers already sent' happens, the cookie is set properly. That doesn't really sound like it should work, but it appeared to work in my testing.
So, the technique I used is
get the current error settings to be used later
turn off display of errors
do things that cause the error (in my case, set the cookie)
restore the error settings to original valuess
Here is the code that I used. Again, probably not 'kosher', but it worked in my case.
// some themes cause a 'headers already sent' message, so we bypass it here
// by turning off that error message while we set the cookie.
// see https://stackoverflow.com/a/26154061/1466973
// $random_guid is a guid set previously
$previousErrorLevel = error_reporting();
Since it worked for my case, I am marking my answer as correct, although the other answer is valid. And I expect a couple of downvotes, as this is not kosher. But it worked for my problem and circumstances.