Make ARAM *feel* random?
What about a shuffle system? (Shuffle = every champion you own, in a random order) It would prevent the "i have all the champions unlocked but still got Udyr 5 times in a row!" while preserving the random aspect of the mode.
Maybe something like: played or rerolled a champion -> it gets marked in the account. Lobby starts -> roll random champion, choosing from the pool of unmarked ones. If there are no unmarked champions left that can be chosen, then unmark all and repeat.