Maritime italian republics are a good candidates, both Genua and Venice had quite big holdings in eastern mediterranean, the apital and the right forma mentis for such an enterprise...
It was said thet Colunbus get the idea of getting to China by a western route by reading Marco Polo book that happened to be wrote in genoise prisons. what if this reasoning was done by a contemporary, may be the same pisan who actually put the Million on paper under the dictation of Polo?
Except that due to Pax Mongolia it was very easy for trade to be conducted overland from Europe to China, so there is little impedus for trade.
I like that a lot.
To respond to several people, yes, the later Powers of Europe were insanely weak at this point. But there were some successful maritime states that, I think, could conceivably have wound up trading with the Americas. Nobody's in any position to make colonies as we are used to seeing them... I think this is the whole appeal of this idea. A totally different dynamic between Europe and the New World, something more akin to that between Europe and Africa or Asia.
I wonder what this would do to the theologians. Their concept of the cosmos was so neat and tidy - a whole new continent would have blown their medieval minds.
I doubt it, especialy since the information would spred rather slowly, and Medieval Europe expected to find strange and fantastic things beyond thier borders. After all there is a long history, especialy in the British Isles, of myths of islands in the North Atlantic.