select a random number between 0&x (x could possibly be half of the highest id num)
with that number (we'll call it $start_num), select a random number between $start)num and the highest id num (max(id))
$x = $row['max(id)'] / 2;
$start_num = rand(0,$x);
$random_id = rand($start_num,$row['max(id)']);