For all reasons mentioned above I can't see any hope of a surviving purely Native "country".
Even an early POD (allowing time for the Native population to recover before the 16th C.) with a rather far-fetched hypothesis (ensuring a limited but [semi]permanent contact so that diseases turn endemic), such as:
- after the death of Arthur Britons sail westwards in search of Avalon / Hy Breasal / the Island of Saint Brendan instead of merely crossing the Channel to turn Armorica into Little Britain / Brittany

, or
- regular contacts with China since the time of Kublai Khan (the Chinese '3rd expedition' having used the Aleutian Island as stepping stones then come across the Klondike gold)

,
supported by a later divergence in Europe (no independent Portugal and a delayed
Reconquista),
a culture fulfilling the requirements to resist the massive European arrivals of late Renaissance would have to no longer be purely 'Native', genetically and culturally.
With a 'moderate' and (relatively) late divergence as generally considered here, I think only a culturally and genetically *hybrid* population can keeps its identity and independence in the long run. Genetically it's the case of OTL Latin America, but in addition it would imply a larger Native cultural heritage.
In North America, think of Riel's French-speaking Catholic half-breeds (but far earlier and on larger scale), and the Seminoles, actually a mixture of 'true' Seminoles, Maroons and the occasional cajun with his half-breed children.
Such 'half-breed' population would be immunized, familiar with 'White' technology and culture -books, farming, metal-working...- and instead of being a patchwork of tribes of diverse religions and languages often with a long history of tribal wars, its members would see themselves as members of a new 'tribe' of their own, united by language and religion. And because its ≥ half European ancestry and culture, it can hope for support from the 'parental' major European Power.
What religion ? Catholics were always far more prone to intercourse with the Natives, the Portuguese specially everywhere they went (all around Africa, India, Indonesia and of course Brazil) sired a substantial population of half-breeds integrated as a new 'class' at the interface between the Europeans and the Natives (I don't want to be banned from my very first post for having a started a flame war, but the major examples of population displacement quoted in the thread -North America, New Zealand, Australia- correspond to Protestant colonizations; and the Afrikaners... ). But a very deviant Catholicism having incorporated more of the Native (and Black) religion than in OTL cohabitation with Native (cf.
Santa Muerte in Mexico...) and African (
Santeria, Voodoo,
Candomblé ...) religious heritage. Jesuits were pragmatic people, a Catholicism 'enriched' with local 'Pagan' tradition along the lines of early Irish Christianity is not too far-fetched.
What tongue ? Had the Portuguese seriously settled in North America it would be (rooted in) Portuguese, they were the most prolific and 'integrating' half-breeds producers. Otherwise a
French Créole, French were less bigot than the Spaniards. In Nouvelle-France the rude Canada-born
coureurs des bois were not the only ones to live 'Indian way', to take a native wife &c..., not a few young
chevaliers from the mother country with an officer commission in the
Compagnies Franches de la Marine 'turned native' for the duration of their sojourn ('Brotherhood of the Wolf', I know, and 'Oumpah-Pah le Peau-Rouge' before, but indeed Grégoire de Fronsac and Hubert de la Pâte Feuilletée correspond far better to the statistical reality than Hawkeye).
I don't know about the Spaniards but French settlers as a rule did not come as whole families Mayflower fashion (a Huguenots in exile colony, as the one which existed in South Africa before its assimilation in the Dutch majority, would be an entirely different matter). The Crown had regularly to send sentenced female thieves and prostitutes to provide them with 'White' wives. It was true in all the colonies (Antilles, Ile Bourbon [La Réunion], Ile de France [Mauritius]...), but in Nouvelle-France North of modern Louisiana there was a large free native population, and no black slaves whose offspring would be discriminated (as in modern Antilles there is still a sharp division between the Black and half-breeds and the 'pure blood White' Békés). The idea of the 'Noble Savage' was constantly present in the culture of well-educated French since Montaigne, and was revived by Jacques Cartier before Diderot and Rousseau.
Where?
'Theoretical' Nouvelle-France was immense, most of it with little or none 'White' population, without colons with 'class' interest (contrary to Algeria later, for instance).A France more interested -and earlier- in the New World could have promoted a Huron / half-breed friendly state
Alternatively,and slightly later, in the Forts Frontenac / Duquesne / Beauhamois / Dauphin / Bourbon polygon and North of it as a buffer against the British around Hudson Bay? Plenty of room, no direct British interference and little in the matter of wrong antecedents there?
http://upload.wikimedia.org/wikiped...p-fr.svg/800px-Nouvelle-France_map-fr.svg.png
(from
wikipedia )
Alternatively, what about a spontaneous (but France-supported from the War of the Quadruple Alliance on) half-breed republic of Barataria type in Florida? Just add French Frères de la Côte and a few Jesuits to an earlier version of OTL Seminoles. Maybe less likely (even more unlikely

), and certainly less 'Native'.