One scenario I've oft pondered is a surviving Byzantium/less of a constant state of war between the Ottomans and Christendom.
It was this closing off of traditional trade routes in the middle east that was a major motivator for the quest to round Africa and find a westwards route.
I think though that even if we don't have explorers actively setting out to find new routes to the Indies, with advancing shipbuilding technology it would be inevitable that fishermen at least would find it in the 16th century- there are those who think Basque and English fishermen were already well aware of the North American coast and it was their stories that led Cabot to get his ideas.
Don't forget that Henry the Navigator was running around well before the fall of Constantinople, and Cape Bojador was passed in 1434. The insane profits to be made from the spice trade are going to tempt somebody to start funding African expeditions at some point, and once they figure out how to bypass Cape Bojador, the end is inevitable.
Early 16th century is about the latest you can pull it off, without an early POD that absolutely devastates Europe.
Someone mentioned the Chinese, but they are much less likely to discover America anytime soon for a host of reasons, chiefly the distance (the Pacific is massively wider than the Atlantic, which makes accidental discoveries much harder, and much less repeatable).