Еще одно индусское решение.
Пусть веса у записей x_1, x_2, ..., x_n.
У каждой записи добавляем поля «начало» и «конец». У i-й записи началом будет x_1+...+x_{i-1}, концом — x_1+...+{x_i}-1. Теперь генерируем случайное число R от 0 до x_1+...+x_n-1 и выбираем запись, у которой начало <= R <= конец. Выбираем столько раз, сколько нужно.
Придется проверять на дупликаты, но при отсутствии сильно перевешивающих записей они будут довольно редки.