With most Kingdoms backing an expedition like Columbus´ you would run into the problem that they are likely to want control over their colonies and are able to secure it. But of course he had some trouble to secure support and was turned down in Portugal, France, England and initally Spain as well.
It might be possible for someone like him to look for backing in the Hanseatic cities, preferably a bit before otl Columbus. Since an expedition starting in Hanseatic ports would end up further north, where there are no obvious riches, but trading opportunities, they might have some time until the Kingdoms wake up to the possibilities of colonies. In the meantime the Hanseatic League can establish Trading Posts. Since they have no control mechanisms for control they might end up as free cities within the League.
Of course it is an outside chance and not going to last indefinitely, but if they are nominally under the HRE, nobody else might see them worth potential trouble with the emperor and they might last long enough to get strong enough to be secure in their own right. And HRE control would be light enough to consider them independent from early on.