Я конечно может сейчас чушь напишу, но:
Итак, выводим с конца одну строку из таблицы путем DESC BY id (если не ошибаюсь).
Примерно так:
$num = mysql_query("SELECT id FROM table DESC BY id LIMIT 1");
Теперь у нас есть переменная, содержащая количество строк в таблице.
Теперь создаем еще одну переменную.
$rand = rand (1, $num);
Ну а теперь выполняем запрос к базе, который тебе нужен, добавив в "WHERE" условие id = $rand
Хз, может быть чушь написал и это тупой метод и вообще может автор этим и пользовался, но я просто написал, как думаю.