Random numbers are defined as a sequence which has no pattern, and therefore no predictability, no matter who looks and no matter what tests) they use. There are problems with finite sequences vs infinite sequences, but we'll not go there.
Random is not in the eye of the beholder -- if the beholder is human. Cats might be very much better, but training them is currently over difficult. Magicians routinely perform parlor tricks asking audience members to produce random numbers. Humans don't do it well at all.
There are some tests for randomness (or that find non-random, many perhaps all?, sequences.) Which is the more or less the inverse problem, of course. Knuth , vol 2, suggests a large number of statistical tests for random sequences, and essentially gives up. These tests will catch some of the most blatant non-random sequences that someone claims is random, but ... By all means, test if you have time, but don't think you problems are over if no non-randomness is found. Might pop up on the test Knuth didn't know about, or the one JoeStat invents tomorrow.
No program running a finite state machine (all practical computers of any architecture, though perhaps quantum computers might be a possibility) can produce a random sequence. It is the nature of a finite state machine.
Some physical processes are believed (with apparently good reason) to be random, and so a reading from such a process might produce random sequences. Both Intel and Via have long built such random number generators into some of their CPUs. Some Silicon Graphics researchers demonstrated that the patterns in a LavaLamp are random (I think I believe this!), and so on. The difficulty is that such processes must be observed and converted into digital information for use. All measurement methods we have are imperfect,and assuring that the method you chose to read white noise from some silicon junction might induce a pattern into the sequences you produce is fundamentally impossible. Can you prove that this is not so?
Some mathematical entities are believed to be random. For instance, pi. The digits which make up its sequence are thought to be random. But there exists an algorithm for finding the nth digit of pi very quickly. What consequence does this have? Or e? Or phi? Or phi? Or ...?
This is a difficult problem. The RANDU routine, from the SHARE algorithm collection, was thought good enough for decades. The random number function in nearly all languages libraries and operating system routines are sadly inadequate. Do not use them without careful investigation. RANDU wasn't random and so much research requiring random sequences may have been flawed. John von Neuman suggested using the inner digits of large squares. But his quote about any one looking for algorithmically generated random numbers being in a state of sin is quite apt.
Randomness appears to be relatively easy to produce, and so many programmers have written routines which claim to be random; which probably accounts for so many library routines being quite non-random. Netscape built one into some early versions of its software until it was proven rather spectacularly to be grossly non-random.
As a practical matter, Shannon's concepts of information entropy are directly relevant. Kolmogorov complexity is in some sense a measure of the entropy of the sequence under test.
In the practical world, in which something purporting to a random number is required, and the randomness of it underpins the security of some security scheme, such caveats are troublesome. No system has sufficient processing capacity to apply all of Knuth's tests, all those other tests, and ... to the random numbers it not only needs but must use.
Hence the concept of cryptographically secure random numbers. Notice the mealy mouth evasion here. These are not random, they are just believed to be "sufficiently random" to be of use in cryptography whose effectiveness (ie, security) is dependent on their randomness.
And, CSRN vary in how random they can be. For instance, stream cyphers require large sequences of random key material to be generated in a short time. The actual encryption function in these is, in principle, the extremely fast machine instruction XOR. If the key generating sequence can be determined security goes poof. A secure, high speed pseudo random generator is required, and furthermore, one (or many) which provide high security.
Other cyphers, such as the various block cyphers, require random keys for security. Those keys must be long enough to be hard to guess in a brute force attack, but if they are non-random no brute force will be required.
Asymmetric key cypher algorithms also require random keys, but they must meet certain mathematical tests, and be so related that the encryption algorithm is really one way, even against well equipped attack.
Poorly designed encryption algorithms are poor and breakable, no matter how well the keys approach real randomness. Can you tell the difference between such an algorithm and a well designed one? Specialists have trouble, so modesty is suggested.
Various schemes have been suggested for CSRNGs, but nearly all are somewhat dubious. For instance, if real world data (disk timings, key stroke timings, network packet timings, ...) is used, what degree of assurance can one have that one's disks (etc) don't have some periodicity that a sufficiently motivated attacker can't discover?
The Linux kernel is sufficiently sensitive to this issue that it has two random routines, one which is quick and will continue to produce "random numbers" on each call, and another which is rather slower, but which produces only random numbers tied directly to various physical parameters in the running machine.
But I suggest you consult Practical Cryptography by Schneier and Ferguson for the design of a CSRNG system they call Fortuna. It goes some way to avoid any entropy limitation from any source, to mix the inputs from each of the (perhaps not entirely random) sources it gets in such a way to decrease predictability as much as possible. It also protects against now unknown attacks against the entropy pool(s) it uses, and to evade attacks against that pool when the machine is off (and so vulnerable to disk theft and analysis). It is not a simple system, but it appears to be quite robust, sufficiently fast for many uses (if not for the entire key sequence required by high speed stream cyphers -- seeds for such a generator would seem very usable however). And the design, and design criteria, are publicly available, a far from trivial desideratum.