Добавлю к ответу
WP Panda ещё парочку более лайтовых вариантов:
1. Мешать товары на каждой странице отдельно. Тогда визуально они будут меняться, но пагинация не сломается и не будет некешируемого RAND.
2. Периодически через cron дергать скрипт, который будет менять порядок товаров в базе. На сайте порядок товаров будет меняться не при каждом открытии, а через заданный интервал времени, но опять же нет возни с пагинацией и проблем с RAND.
Не знаю какая у Вас точная задача по ТЗ, но если использовать один из способов или совместить их, то можно добиться неплохого визуального эффекта псевдослучайности.
P.S. Способ №2 содержит потенциальную проблему в случае, если порядок товаров в базе изменится во время того, как пользователь просматривает каталог. Поэтому этот сценарий тоже стоит как-то обрабатывать.