А чим можна користуватись?

Такі задачки в компаніях як гугле часто завершуються досить неочікуваними результатами, наприклад ця завершиться тим, що немає повної випадковості, є псевдовипадкові події, тож висновок - лохів які спробують вирішити цю задачу до біса і жоден не скаже цього, відповідно роботи їм не очікувати.

Якщо кількість елементів відома з самого початку, то користуємося будь-яким генератором випадкових чисел, отримуємо номер необхідного елемента, і починаємо чекати його прибуття.
Якщо кількість елементів завчасно не відома, то можна періодично обирати елементи у масив, а в кінці з цього масиву обрати наш випадковий.

Якщо пам'яті у нас зовсім мало, то можна утворити ієрархію з кількох внутрішніх масивів A, B, C... Коли масив A переповнюється, він віддає випадковий елемент масиву В, а сам очищується для нових елементів. Те саме робить масив В, і так далі.
Десять-п'тнадцять таких масивів, і гугол уже не видасться великим числом.
Обирати можна або через випадкові проміжки часу, або взагалі не обирати, а пхати у А все підряд.

а може хтось в коді реалізувати власну функцію генерації випадкових чисел?

я не знаю що таке рівномірний розподіл і мене це в принципі не дуже турбує. спочатку подумав що це мається на увазі генерація випадкових чисел.

Коли отримуємо n-тий - з ймовірністю 1/n замінюємо на n-тий...
Проблема в тому, n на практиці - обмежене. Нехай max(n) - максимальне число для типу n і нехай ми можемо генерувати рівномірно розподілене ціле число від 0 до max(n)-1.
При n=max(n) можна ввести нову змінну x2 і спочатку привласнити їй значення  max(n)+1-го елементу, потім з ймовірністю 1/2  max(n)+2-го і т.д.
Коли дійдемо до  2*max(n)-го елементу, привласнимо х з ймовірністю 1/2 значення x2, і привласнимо х2 значення 2*max(n)+1-го елементу...
Коли дійдемо до  n2*max(n)-го елементу, привласнимо х з ймовірністю 1/n2 значення x2 і т.д.
Таким чином, зможемо охопити max(n)^2 елементів.
Далі можна брати x3, привласнювати йому max(n)^2+1 значення...
Можна створити масив з x, x2, x3, ..., інший - з лічильниками n, n2, n3, ... Для гугола шести елеменів в масиві достатньо (якщо брати тип System.Int64 в .NET).
P.S. Оремо треба прописувати процедуру, коли отримуємо останнє число послідовності.
Тому, можливо, для коректних розрахунків замість max(n) краще взяти max(n)/2.

Алгоритм корисний наприклад якщо ми хочемо вивести випадковий рядок файлу, і не хочемо читати ввесь файл щоб дізнатись скільки там рядків. Ну і в інших подібних ситуаціях.