В таблице может не быть записи с таким id Что тогда делать?
PHP:
list($id_min, $id_max) = mysql_fetch_row(mysql_query('SELECT MIN(`id`),MAX(`id`) FROM table'));
$id_var1 = rand($id_min, $id_max);
mysql_query("SELECT * FROM table WHERE `id`>={$id_var1} ORDER BY `id` ASC LIMIT 1");
Но такое решение увеличивает вероятность выборки той записи, которая стоит после дырки. И чем больше дырка, тем больше эта вероятность.