Aqui está um método que você pode usar:
<?php
$num= mt_rand();
$con = mysql_connect("localhost","uname","password");
mysql_select_db("dbname",$con);
$sel_query = "SELECT * FROM my_table WHERE rand_num =%d"; // query to select value
$ins_query = "INSERT INTO my_table(rand_num) VALUES(%d)"; // query to insert value
$result = mysql_query(sprintf($sel_query,$num),$con);
while( mysql_num_rows($result) != 0 ) { // loops till an unique value is found
$num = mt_rand();
$result = mysql_query(sprintf($sel_query,$num),$con);
}
mysql_query(sprintf($ins_query,$num),$con); // inserts value
?>