SNG... I think this is a great argument against the use of information theory to puportedly debunk evolution. In that context, pure randomness is indeed the issue.
But when most people say 'by chance', I don't think they really mean 'purely random'. I think they mean non-linear/chaotic/non-directed.
For example the result of a coin flip is not truly random. It is determined by aerodynamics, and by the exact location and strength of the flip. Sill, most people (yourself probably included) would call it 'random', and say that it came up heads or tails 'by chance'.
So when most people complain about evolution being 'random' or 'by chance', I don't think that actual mathematical randomness is what they're referring to.