Можно попробовать рандомизировать только id. Однако это не панацея. Выборка случайных данных при больших объемах медленная и с этим ничего не поделать.
На php генерируй случайный id, который можно сделать между min(id) и max(id) из бд.
Правда это еще один селект к бд для получения макcимума и минимума id.