I also believe that new information would be required to be added to the DNA of any creature before it could evolve from a previous form.
Since there is no way to introduce new information into the DNA evolution is impossible.
Ever heard of gene duplication? That's when DNA recombination gives rise to a copy of a gene, which then acquires mutations that make it produce a different protein and serve a different function in the organism. That's what accounts for the families of globin genes that code for proteins that perform various metabolic functions in living cells.
I don't think the information analogy is as useful at the cellular level as you appear to. However, gene duplication and divergence certainly constitute the metaphorical new information you consider crucial to evolution.