Hola:
Basándome en un paginador que hice en Ajax:
Ajax: Galería de imágenes paginada, la teoría que uso es obtener todos los elementos (sus claves) y ponerlos en un array y luego para rescatarlos uso in... o sea para obtener ese array se debería poner order by rand()...
select clave from tabla order by rand()...
where $clave in ($items);
En esa página se puede ver el código ajax para buscar esos datos.
Saludos
