Variable available everywhere in template?
$variables are unique for each template. So if you implement hook_preprocess_html() and add something, then it is only available for html.tpl.php and nothing else.

I think the easiest way to achieve your goal is to create a new function in your template.php which sets the random color them the first time you access it and the returns the them on following calls. Then you can simply call that function from any template you want and it will return the same value on the same request. Such a function would look like this:

function yourtheme_get_color() {
  static $color = NULL;

  if (!$color) {
    // First call, define $colors here and then set $color.
    $color = $colors[array_rand(Array('red', 'blue', 'magenta', 'green' ), 1)];
  }
  return $color;
}