get random value from a PHP array, but make it unique

You almost have it right. The problem was the unset($arr_history[$selected]); line. The value of $selected isn't a key but in fact a value so the unset wouldn't work.

To keep it the same as what you have up there:

<?php

$arr = $arr_history = array('abc', 'def', 'xyz', 'qqq');

for ( $i = 1; $i < 10; $i++ )
{
  // If the history array is empty, re-populate it.
  if ( empty($arr_history) )
    $arr_history = $arr;

  // Select a random key.
  $key = array_rand($arr_history, 1);

  // Save the record in $selected.
  $selected = $arr_history[$key];

  // Remove the key/pair from the array.
  unset($arr_history[$key]);

  // Echo the selected value.
  echo $selected . PHP_EOL;
}

Or an example with a few less lines:

<?php

$arr = $arr_history = array('abc', 'def', 'xyz', 'qqq');

for ( $i = 1; $i < 10; $i++ )
{
  // If the history array is empty, re-populate it.
  if ( empty($arr_history) )
    $arr_history = $arr;

  // Randomize the array.
  array_rand($arr_history);

  // Select the last value from the array.
  $selected = array_pop($arr_history);

  // Echo the selected value.
  echo $selected . PHP_EOL;
}

http://codepad.org/sBMEsXJ1

<?php

    $array = array('abc', 'def', 'xyz', 'qqq');

    $numRandoms = 3;

    $final = array();

    $count = count($array);

    if ($count >= $numRandoms) {

        while (count($final) < $numRandoms) {

            $random = $array[rand(0, $count - 1)];

            if (!in_array($random, $final)) {

                array_push($final, $random);
            }
        }
    }

    var_dump($final);

?>

How about shuffling the array, and popping items off.

When pop returns null, reset the array.

$orig = array(..);
$temp = $orig;
shuffle( $temp );

function getNextValue()
{
  global $orig;
  global $temp;

  $val = array_pop( $temp );

  if (is_null($val))
  {
    $temp = $orig;
    shuffle( $temp );
    $val = getNextValue();
  }
  return $val;
}

Of course, you'll want to encapsulate this better, and do better checking, and other such things.