There are few ways to generate truly random numbers on computers. There are lots of ways to get pseudorandom numbers. They're pseudorandom because they in general are produced by an algorithm that is completely deterministic. Other factors in chosing a random number generator are range, distribution, and integer vs floating point. For your problem and using the VEX controller, integer is sufficient and you don't need much range. Most algorithms you'll find produce numbers from a uniform distribution. If you needed a Gaussian distribution, you'd need to do a little more work. But since it appears you're just trying to fool humans, a uniform distribution sounds adequate.
A simple pseudorandom number algorithm that the VEX could easily handle is based on progressively squaring and truncating a number. Start with a seed, square it, and truncate so you preserve the low order bits. For an 8 bit case squaring gives you a 16 bit number. Throw away the upper 8 bits and keep the lower 8 as your random number. Use that random number to generate the next one in the same way, ad nauseum.
Other more complex arithmetical operations can prevent the zero problem such as adding a constant at each iteration. But this isn't really any different than simply restarting with the original seed on detecting a zero. Once you generate a zero, you begin a cycle that will eventually repeat.
One problem most pseudorandom numbers share is that eventually, they generate a random number they've generated before. Since it's used to generate the next one via a fixed algorithm, you end up with a cyclic series of numbers. If the cycle is long enough and has reasonable statistical properties, it may still be useful. It depends on the application.
A problem with some and particularly the simple one I mentioned above is that one of the possible random numbers is zero. Squaring zero gets you zero back from here to eternity. Sounds like a good movie title.

One way to avoid this is when you detect a zero, to chose a new seed for the next iteration. If the computer has a real time clock, that could be read to determine a new seed. Or on a PIC you could let a timer run freely and read it to get a new seed. Presumably, with different paths through the program and the "randomness" of the algorithm, you'd get a reasonable distribution of hits on the values from reading the timer. Depending on how often you needed a random number and the varibility of paths through your program, you could just read the timer to generate your randoms. However, you could be reading it quickly enough that you'd always have ascending sequences until the timer rolled over.
If you needed truly random numbers, you could use an analog input and read something like the thermal noise in a thermocouple or use radioactive source and count the radioactive decay events in a given time.
As to controlling your video source, I assume you're using a VCR or DVD player. You could tap into the play button and substitute a relay that could be controlled by a digital output from the VEX controller. Probably void your warranty.

Another would be to buy or build a device that the VEX can control that generates the infrared remote signal. I have no idea if these are available commercially but certainly the components are readily available. I suppose yet another way would be use a solenoid that physically pushes the button and is controlled by the VEX. And I suppose some newer high end systems might actually have some kind of computer interface you could hack into.