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