A ver si entendi bien , no se como tengas implementada tu paginacion pero me imagino que es como de este tipo
http://www.desarrolloweb.com/articulos/1035.php
si asi es podrias organizar el resultset en forma de un arreglo y que la funcion
http://www.php.net/manual/es/function.shuffle.php
para cuando lo vayas imprimiendo pues salga en orden aleatorio