Сделать скрипт, который будет перемешивать данные (генерировать случайное число для каждой записи), но это будет тяжёлый запрос, если записей в таблице много
UPDATE `table` SET `random` = RAND()
И потом выводить с сортировкой по данному значению
P.S. Можно генерировать случайные числа на первой странице, а на остальных не генерировать