Yeah, I guess it depends. As Mu naught said, relativity is an example of theory coming before experiment. Black holes are another. They were predicted by theory long before we started seeing astronomical images of them. But in my line of work, experiment often comes before theory. For example, the relativistic high energy jets emitted by active galactic nuclei were not predicted by any theoretical model. They were first detected by gamma ray telescopes, and the theorists are now coming up with models to explain their astrophysical origin.
I guess this is another example of how neither theory nor experiment is more important in physics. Both approaches need each other in order for new discoveries to be made.
I think we are currently in a situation were this paradigm changes (even for relativity there were experimental results).
In the context of quantum gravity there are a few theoretcal approaches (loops, strings, ...) which can never be directly tested experimentally. Nevertheless one tries to formulate a consistent theory of quantum gravity. This is required not be experimental results (there is not one single result which forces us to give up classical GR), but due to the inconsistency of the direct quantization of GR + matter interaction.
I know that this is dangerous for physics in general as it may lead to speculative theoretical ideas not controlled by experiments. But I see no alternative but to investigate these approaches further w/o stopping here and come to an end in physics.
I think it changes with time. The more we know the less likely it is to find something accidentally during experimental work. So 200 years ago any experiment could lead to discovery, today it is much easier to predict we may see something and design an experiment around the prediction.
I think that we are in a situation where experimental progress is - due to first principles - not to be expected for quantum gravity. It is not that we know too much about quantum gravity; experimentally we know (nearly) nothing about it. That means we must study a class of theories w/o having ever the chance to set up experiments providing experimental guidelines.
But as quantum gravity is only one rather special topic I will stop now to insist on it.