Evolution is testable (and, more importantly, falsifiable) because it can make statements about what should not exist if it is true. This is the proverbial "rabbit in the Cambrian". Basically, if we were to ever find a fossil that does not belong (after eliminating factors such as shifting of rock or some other explanation), then it would actually disprove evolution.

This has not, and more than likely will not ever, occur.

Additionally, evolutionary theory has made predictions about both the types of fossils we will find as well as living creatures that should exist. This is not in itself proof of evolution (a Creationist/ID-er could postulate that some creature would exist because a designer would want it... but it would not be via a logical conclusion).

The books Why Evolution is True by Jerry Coyne and especially Greatest Show on Earth by Richard Dawkins address both of these quite thoroughly.

I might add that Darwin- at the very least- ended up making two very big predictions that could have falsified his theory.

The first is that there was a mechanism that would save and perpetuate favourable traits. There was little understanding of how this was done at the time. In effect, Darwin had to predict that 'modern genetics' would come into being.

The second is that he predicted that the earth had to be very old. But time is a necessary factor in the ToE. Again, many geologists had an inkling that this was true. In the end Darwin was correct- deducing this from his observations about the natural world.

These were big, sweeping predictions of the time. I'm not sure that there is much scope for these big predictions anymore. If we're thinking of more recent examples, it would be the ability of the genes in an organism to innovate. In order for new species to emerge, it has to be that the genes in a population are an open- not closed- set. Otherwise you're just reordering the frequencies of different genotypes. But studies with microbiological organisms have shown that such innovations do occur- that the genes are not a close set.

In the main, common descent predicts that there all life derives from a number of common ancestors. So a completely novel life-form that does not share the genetic similarities of others, would go someway to discomforting the theory.

Modern and ancient fossils commingling would be fairly embarrassing (the rabbit in the Cambrian).

A Pre-Cambrian Panda.

I think the other issue is that we have now such a massive convergence of genetics, dating techniques, fossil record, geological column, biogeography and anatomy, plus observed evolution with micro-organisms, there is no single test that would refute the theory.

Note that biologists persisted with the Theory of Evolution even after Lord Kelvin said the earth wasn't old enough to permit speciation. Kelvin's ignorance of radio-active elements meant that his estimate was wrong. Plus the fact that his calculation conflicted with geological evidence, didn't make it compelling.

I think we are really at a point where we would need a broad class of facts that conflicted with everything we observed to date in modern biology. And we would also need an alternative model that explained the facts better.

It would help if there was a competing theory that made testable predictions.

Edit: I'm not even sure the hypothetical rabbit or panda out of place in the fossil record would necessarily invalidate evolution. Since the fossil record is incomplete, it's possible that we might discover an extant animal with a unknown, far distant evolutionary origin and limited change since, which we have mistakenly placed in a different lineage. We have creatures such as the coelocanth and horseshoe crab that have long legacies of little change yet are still alive. I suppose rabbits and pandas are probably bolstered in their position in the evolutionary model by evidence from molecular biology, rather than simply morphological characteristics, so they might be sufficient to raise serious questions, but the issue remains: what is the better theory, that better explains all the evidence available, and creates testable, falsifiable, predictions? If something is proposed, then we can evaluate it and perhaps it will replace current models, but nothing has stood up to scrutiny nearly as well as evolution. What has been proposed so far in the form of ID and creationism is not science, does not have scientific bases, and despite claims to the contrary by proponents, does not hold up to scientific analysis in the slightest.