Можно создать memory table из айдишников всех записей, удовлетворяющих условию, и проставить этому списку нумерацию (id(auto_increment), id_from_query) - в итоге берем max(id) из мемори тэйбла, и вызываем пять раз рандом от одного до макс айди. Дальше думаю понятно.
SELECT * FROM (
SELECT id AS user_id, count(id) AS message_count
FROM wall_messages
GROUP BY id) AS list
LEFT JOIN users
ON users.id = list.user_id
ORDER BY list.message_count DESC
LIMIT 4