Is there a rule/method to know how "random" should the cube be when solving it? in order for it to be a "valid" score?
The World Cube Association has regulations regarding the official scrambling algorithm used for their competitions.
An official scramble sequence must produce a random state from those that require at least 2 moves to solve.
Basically, as long as it takes at least 2 moves to solve, it's a valid scramble. All scrambles are computer-generated.
Most scrambles will require a minimum of 18 moves to solve. The number of possible permutations for a certain number of moves is given on http://www.cube20.org.
Although a 2-move scramble is in theory possible, the chance of it happening is about 243 in 43 quintillion.
I seem to recall that the standard for competition scrambles before this was 40 random turns, but I don't have a source for this.
A rubik's cube cannot be more than 20 moves ([called God's number]) away from its initial position.
After about 16 moves, you should be random enough, since it's very hard to be in a specific 20-moves-away position.