Evolution does not hold that random change produces information. Rather, it is random change combined with selection that produces information.
Don't you think random change produces information? It also produces noise. Selection insures that the information to noise ratio is kept to a minimum. But it is indeed the random changes (of course, in the context of biology is not truly random) which produce the variation we see in evolution.