Can random mutations cause an increase in information in the genome?

Yes. In the bacteria Flavobacterium and Pseudomonas the ability to break down nylon arose through selection and mutation. In Flavobacterium the enzymes required to perform this reaction were produced by bacteria living in the wastewater from a nylon factory, at some point in time after nylon was invented. Pseudomonas produced a different set of enzymes that catalyzed a similar reaction when scientists cultured it under laboratory conditions.It is important to note that for new information to come about, a selective force must act upon mutations. If there were no selection, random sequences of nucleotides would arise, rather than usable genes. Bacteria that could hydrolyze nylon were more likely to reproduce than bacteria that could not, so that particular mutation became more prevalent as time went on, until nylon-digesting bacteria were the norm in that population.

If the result is beneficial I don't see how it the mechanism that caused it is deleterious. It seems like your definition of "deleterious" is pretty arbitrary.