This is a very tall order. For various reasons, none of these nations had much of a merchant marine during the middle ages, making it difficult for them to take the lead in transatlantic settlement and exploration. Ireland and Wales never really formed lasting national kingdoms, leaving Scotland as the only possible option. Scotland had the advantage of being relatively close to Canada, New England and Nova Scotia, but the misfortune of being constantly threatened by a stronger power to the South (England).
If Scotland was every going to get a head start on the new world exploration, it would probably under James IV. James IV was intelligent, inquisitive, and generally a good organizer. He built up the Scottish navy almost from scratch in order to bring rebellious isles to heel, and, just as importantly invested in building port facilities to continue the expansion of his navy. If Henry VII had been distracted, broke, or otherwise disinclined, James IV MIGHT have been able to secure the services of Giovanni Cabutto (John Cabot) to explore the New World, and lay claim to Newfoundland and other parts of North America for Scotland.
If Scotland was vastly more successful during their invasion of England, and, say, forced England to pay tribute, Scotland would be in a good position to stake a claim to the New World. Relations with France would be cordial enough for them not to interfere (and France would soon be distracted by religious strife). Between 1515 and 1559 (while Europe outside the Iberian Peninsula was completely distracted by the Italian Wars), Scotland would have its window to expand in North America. Newfoundland and Nova Scotia would seem like obvious targets because of the nearby fishing grounds, and climate being comparably similar to Scotland's.
Expansion in South America would be unlikely for several reasons. Spain dominated that territory from the start, and Scotland was a co-belligerent of Spain's enemy, France.