The random requirement serves two purposes. First, it makes sure the random-number sequence creates a unique treap. Second, it makes sure all possible random-number sequences are equally probable.
A random-number sequence doesn’t have to be unique (in fact, you could argue that a unique sequence of random numbers from a finite domain isn’t random). However, generating a sequence of unique random numbers is easy: catenate a random number with a strictly monotonic number sequence. The monotonic numbers provide uniqueness and the random numbers provide randomness. (You could argue the result isn’t a unique random sequence if both numbers are drawn from finite domains, as is the case with fast implementations on digital computers. However, using 32-bit integer domains for both numbers, the time it would take for the sequence to repeat itself falls somewhere on the other side of the universe’s heat-death.)