Я думаю, что это лучший возможный способ.
SELECT id, id * RAND( ) AS random_no, first_name, last_name FROM user ORDER BY random_no