It's not the individual base pairs that matter - it is the order they are in, how many there are, and so on.
Think of it like the english language: it is perfectly possible to invent a new word, without having to invent new letters.
The molecular mechanism for evolution at the gene/protein level, which you are asking about, it not 100% understood, but a couple of important points to remember are:
 gene duplication.
It is possible for DNA replication errors to result in a gene being copied twice. Obviously, this isn't normally detrimental, as the cell's feedback mechanisms will ensure only the right amount of the final protein is made, but what it *does* allow is for divergence between the two genes. Maybe a mutation occurs in one of the genes, but not the other, changing how the protein works or what cells it is found in. This has happened in the vertebrate eye lens, where many of the crystallin proteins found in it are actually versions of other proteins that perform different jobs elsewhere in the body. In the diurnal gecko, a retinol-binding protein, normally found in the blood, became duplicated, and then became expressed in the lens - where it acts like "sunglasses", filtering out harmful UV light.
 domain shuffling.
Often entire bits of proteins are rearranged by DNA mistakes - for example, adding a membrane-association domain to a protein that was previously cytoplasmic. This will change the protein's location, and therefore its function.
 gene deletion
Entire genes can be excised from the genome.
These kinds of mechanisms are what can create "new" genes (or remove old ones), and then change them without effecting the original gene and its function.