In this paper we study the problem of evolving 2-dimensional Cellular Automata (CA) as Pseudo-random Number Generators (PRNG). First, we introduce a composite fitness metric that incorporates elements from PRNG tests, and which is more suitable for evolving CA. Second, we apply and verify this composite metric on two different use-cases: First, to evolve Additive CA as PRNGs using Genetic Algorithms and second, to evolve Totalistic CA as PRNGs using a Markov Chain Monte-Carlo approach.