1) В PHP собираете массив из данных (сначала 20 шт $a, потом 50 штук $b и т.д.)
2) Применяете к массиву функцию shuffle()
3) Записываете все данные из массива в БД
Либо добавить поле с временем добавления, и делать выборку по нему.
Либо при каждом запросе сохранять куда-нибудь последнюю новую запись интервала, и по ней ориентироваться какие записи новые (этот вариант очевидно хуже).
