Lets say I have 1000 bytes that are supposedly random. I want to verify to a certain certainty that they are indeed random and evenly distributed across all byte values. Aside from calculating the standard deviation and mean value, what are my options for a robust verification process?
You can't. Randomness is a property of the source, not a property of the values you get from that source. In other words, randomness is a statement about the probability distribution, not about some specific values sampled from that distribution; from a finite sample, you can't give a definite answer to your question.
Or, to quote Dilbert:
What you can do is perform some kind of statistical test, with the properties that (a) if it is truly random, it'll probably be accepted, (b) if it is not truly random, it might be accepted or might be rejected (no guarantees). In other words, if the statistical test rejects it, then odds are it wasn't random. However, if the statistical test doesn't reject it, you can't conclude anything -- it might be random, or it just be a good enough mimic to fool that one statistical test. Such statistical tests are often sufficient that they can reject many obviously-bad generators.
If that sounds like the kind of thing you're looking for, look up the DIEHARD test suite and related tools.
The best-effort verification is to estimate min-entropy. There are many, many ways to do that, each having their own pitfalls.
One interesting approach is to use algorithms that try to predict the next value using the previous values, as was explored in the paper Predictive Models for Min-Entropy Estimation. The paper also references the NIST Special Publication 800-90b (draft) which covers some methods for estimating min-entropy. You can find more information about random number generation at NIST's Random Number Generation page.
This is all much more relevant to random generators meant to be used in cryptographic contexts.