Если скорость исполнения не критична (что маловероятно но вдруг) можно обойтись без random, а сортировать строки по хешу от crc32(row_id*MAX_USER_ID+user_id) или представив числа как строки например:
select * from table order by md5(concat(id,'|',$user_id))
советую использовать числовые хеши типа crc32, по уму они быстрее.
MAX_USER_ID это максимальное значение user_id, что бы значения не пересекались, так как если просто сложить id+user_id то 1+3 выдаст тот же результат что и 3+1. Можно чуть сократить сдвиг (особенно если хочешь поместить результат в 32-битный int), если убрать из интервала неиспользуемые минимальные user_id - id*(MAX_USER_ID-MIN_USER_ID)+(user_id-MIN_USER_ID). И конечно можно битовыми сдвигами пользоваться.
Достоинство - это полностью вычисляемый алгоритм, ничего хранить не придется.
Недостаток подхода - каждый раз при запросе будет сканироваться (и вычисляться хеш) вся таблица, в т.ч. и при пагинации, но нагрузка останется на базе данных. Но так как любое эффективное решение потребует где то хранить порядок для пользователя, можно и тут просто сохранять хеш в специальной таблице и считать его однократно.
Второй недостаток - новые записи могут попасть в начальную часть списка, которую пользователь уже прочитал, т.е. все статьи в результате сдвинутся вперед. Это можно частично решить (статью, появившуюся в начале, пользователь так и не прочитает), если пагинацию делать не постраничную, а записи по ее id, т.е. в интерфейсе есть next/prev но нет номера страницы (в ссылке id записи или ее вычисляемый хеш).
p.s. как пользователь скажу, что этот подход лучше не применять, мало того, как пользователь я не вижу пользы в случайных статьях.
