Пусть A — результат SELECT MAX(id) FROM `my_table`(его вполне можно хранить отдельно в key-value-хранилище и иногда обновлять)
Генерируем число от 1 до A включительно, пусть это B на стороне клиента (в данном случае — php приложения).
И выбираем первую запись, id которой >= B (SELECT `pole` FROM `my_table` WHERE `id` >= B LIMIT 1)
Попробуйте. Должно помочь.
