Мне нужно выбрать случайные четыре записи из всех записей, удовлетворяющих критерию.
Просто выборка выглядит так:


Я так понимаю, если у меня в таблице нет столбца с рандомными числами, то мне остается только считывать ВСЕ записи в массив, а уже оттуда брать случайные?

когда ты пишешь тему вопроса, тебе показывает темы с похожими названиями.
ты правда думаешь, что первый столкнулся с такой проблемой?

Ну я нашел похожую тему - но там так и не нашли изящное решение   

решение изящное: order by rand()
коротко, ясно и медленно :( по крайней мере - потенциально медленно, потому как using filesort - никакой индекс использовать не получится.
с другой стороны, "внешне" громоздкое, но по сути - удобное решение: генерирование id случайных записей на стороне клиента и на основе этих сгенерированных создание соответствующего запроса. 
Если эти твои случайновыбранные записи учавствуют в join или подзапросе, может быть некислый выигрыш в производительности.

begin, извини, родной, но "мне остается только считывать ВСЕ записи в массив" и "не нашли изящного решения" - это две большие разницы. Это во-первых.
Во-вторых, сама задача делать рандомную выборку - неизящная. Нет ни одной осмысленной причины делать абсолютно рандомную выборку по большой базе - подойдет псевдо рандомная. А по маленькой вообще не нужно париться - любое будет изящным.