The 1497 English expedition led by Italian Venetian John Cabot (Giovanni Caboto) was the first of a series of French and English missions exploring North America.
North America isn't Mexico and Newfoundland is a lot closer than Mexico and you don't have Spain there already.
In 1520–1521 the Portuguese João Álvares Fagundes, accompanied by couples of mainland Portugal and the Azores, explored Newfoundland and Nova Scotia.
At that time the main interest was Asia and those were private expeditions to a place where Spain had no settlements.
In 1524, Italian Giovanni da Verrazzano sailed at the behest of Francis I of France, who was motivated by indignation over the division of the world between Portuguese and Spanish. Verrazzano explored the Atlantic Coast of North America, from South Carolina to Newfoundland, and was the first recorded European to visit what would later become the Virginia Colony and the United States. In the same year Estevão Gomes, a Portuguese cartographer who'd sailed in Ferdinand Magellan's fleet, explored Nova Scotia, sailing South through Maine, where he entered New York Harbor, the Hudson River and eventually reached Florida in August 1525.
Giovanni was a expedition to show that they could go there and Estevão sailed under Spain to those areas not under Portugal.
From 1534 to 1536, French explorer Jacques Cartier, believed to have accompanied Verrazzano to Nova Scotia and Brazil, was the first European to travel inland in North America, describing the Gulf of Saint Lawrence, which he named "The Country of Canadas", after Iroquois names, claiming what is now Canada for Francis I of France.
Is it really so implausible that any of these OTL voyages couldn't have taken place prior to 1519, and couldn't have gone to Mexico before the Spanish did?
The problem of all the expeditions you shoe was that they were all to North America and they were just to explore unclaimed land. In contrast the Mexican golf had Spanish presence in the area and when the riches of Mexico are found they would protect the area from other European powers. You basically have to butterfly Columbus to ensure that there are no other European powers in the area to allow the other countries to conquer Mexico.