Most great scientific advances take place before there is evidence for them. Scientists follow their hunches, then collect data which they hope will substantiate those hunches. Indeed, there is often evidence to substantiate the opposite view. That is what determines great scientific advances from mediocre ones: the great ones see through the existing evidence as understood at the time to posit new ideas which require different evidence or at least a (sometimes drastic) re-interpretation of existing evidence. This model may now be under threat from historically new scientific methods (see Michael Nielsen’s Reinventing Discovery) but it has been this way to date.
Similarly in mathematics, advances are made when mathematicians feel there is a proof of a relation or a pattern to be found. Following their intuition, they inch their way towards the result, often guided by strongly aesthetic motives and often making wrong turns and taking detours before they arrive at the proof which is evidence for the initial hunch.
Outside of science and mathematics, moral advances are made – for example in extending voting rights to women or rights in equality to homosexuals – when first individuals and then groups make the case that the status quo is morally unacceptable and must be changed. There is usually nothing we could call evidence for these claims at the time they are proposed and even afterwards what we might call evidence for the importance of these advances is sometimes hard to establish, at least without invoking other norms which are disputable. Yet I hope no right-minded person would dispute that many such moral advances are, indeed, advances.
Progress is therefore made in many, if not all, of the most important aspects of human life, by moving forward, experimenting, creating and analogizing before there is any evidential justification for doing so.
Evidence is then a vital sieve, a constraint, a monitor, sifting the good from the bad and eliminating the worst, but it comes after the facts and data are gathered to test the new ideas, new theory. It can rarely, if ever, be a pre-requirement for the best ideas.