As already stated, the Mi'kmaq almost accomplished this OTL if not for a serious outbreak of disease. The Hawaiians, although based differently geographically, actually did achieve independence and recognition up until their annexation by the US. The key features that allowed them to survive was, as far as I can see, 1) a willingness to adopt European ideas, technology, and religion, and 2) a lack of naturally occurring precious metals making them worth more as trade partners than as direct subjects to the Europeans. As the Mi'kmaq are already taken and the Hawaiians would be cheating, I'm going to "create" a civilization fitting the criteria.
I would like to nominate the Pueblo. The leader is going to be Po'pay. In 1680, the various Pueblo tribes successfully carried out a revolt, forcibly ejecting the Spanish from their lands. The Spanish attempted reconquest in 1688, but lost. In 1692, the Spanish returned again -- with more guns -- and successfully negotiated the surrender of the Pueblo against promises of leniency and religious tolerance. The exception was the Hopi, which due to their geographic insignificance and small numbers were more-or-less ignored and allowed independence up until they asked the US to help secure their defense against the Navajo in 1851, after which they were promptly made subjects of the US.
The interesting part of the Pueblo revolt is the reasons for the surrender of the Pueblo federation:
1. The revolt was riddled with millenarianism. Many of the Pueblo genuinely believed that the old Pueblo gods would reward them for driving out the Spanish. When rewards failed to materialize, enthusiasm was partly lost. After the revolt, the nearby Navajo people began a long and brutal series of raids against the Pueblo, taking slaves and stealing crops and causing a famine. Up until then the Spanish had kept the Navajo at bay, but the Pueblo state did not have the technological advantage or the centralized government necessary to properly respond to the threat.
2. Pop'ay supposedly wanted to set himself up as the "monarch" (or theocratic leader) of the federation, The Pueblo objected, and Po'pay was deposed and killed in 1681, a year after the revolt.
3. Anti-European sentiment (especially by Po'pay and his followers) caused the Pueblo to embrace isolationism and carry out several acts of self-sabotage -- wheat and barley were seen as "European" crops, and so fields planted with these were left to die. Similarly, the use of European weapons, European livestock, and so on was (supposedly) outlawed.
4. The Pueblo had little-to-no experience with central government, and apart from the followers of Po'pay sought a return to the traditional lifestyle of self-governing villages. As such, the Pueblo could not respond to Spanish or Navajo threats in an effective manner, despite the numerical superiority for which they actually had the capabilities.
5. The Spanish response in 1692 exceed that of 1688 primarily because it was feared that the Pueblo had allied with the French. The Pueblo, lacking the organization and hating Europeans enough to never even consider establishing such an alliance did have French support, but it was conceivable that they could have had French support.
With that in mind, I think it is possible to help the Pueblo maintain their independence. Mainly, we need to replace their xenophobia and isolationism with a willingness to adapt European ideas and an openness for trade -- something like the Mi'kmaq, in fact. Let's say that the monks left behind to convert the Pueblo after Vázquez de Coronado's conquest of the Rio Grande are a bit less fire-and-brimstone, and a syncretic Pueblo-Catholic tradition develops as a result. Similarly, perhaps the Pueblo notice that the presence of the Spaniards seems to reduce the amount of raids from the Navajo, and that some of the European crops have better yields. The Spaniards, being Spaniards, would still seek to exploit the Pueblo for labour and impose catholic orthodoxy in place of the syncreticism. A philosophy develops where some of the European ideas are kinda good, but the Spanish are still tyrants and oppressors. As such, Po'pay is still put on trial and almost executed for witchcraft, and the revolt still happens. However, the philosophical underpinings of this revolt are different.
The Pueblo attempt to syncretize Spanish government as they have done with Spanish religion, and are okay with Po'pay taking central power. He is not deposed as he was OTL, but instead crowned King of the Pueblo. Owing to the tradition of syncretism, instead of focusing his efforts on destroying any-and-all European influence upon Pueblo society, he focuses on centralizing the government and securing the future of the Pueblo nation -- by any means necessary, as he is accused of OTL. He creates an official army in response to Navajo raids, successfully avoiding famine. He establishes a trading relationship with the French, who are happy to deprive the Spanish of profits from the now Puebloan sugar plantations. In 1692, the Spanish still show up with enough guns to force the surrender of the Pueblo. However, instead of a ragtag group of native chieftains, the Pueblo are lead by a more-or-less Christian king, who by European philosophy of the time can be negotiated with. They monopolize the sugar trade and force the Pueblo to allow Spanish missionaries in Pueblo territory, but otherwise leave the pueblo as a de facto independent client kingdom. Eleven years later, the Pueblo take advantage of the War of the Spanish Succession, formally ally themselves with the French, and gain the recognition of the French crown as a "reward".
From thereon, the Pueblo survive by being the biggest fish in their small pond, and by trading with the much larger French- and Spanish-speaking fish in the neighbouring ponds -- naturally, playing them off each other as much a possible. They are probably eventually annexed by either the US or Mexico, but they at least have a few centuries of independence and a fighting chance against any invaders.