In the book I'm writing, a sibling group among my characters are 1/4 Native American.
I first chose the tribe. Since I knew where they lived (a fictional small town outside a real-life larger town in Arizona), I looked up which modern-day tribes existed and picked the one that seemed most likely.
Next, I looked up the website for the tribe and read through their public documents. It's a small tribe so I also did this for a tribe nearby that it is affiliated with.
I was only looking for English names and surnames, so the public docs had plenty. I also didn't want to choose anything that might turn out to be unique to one person/family who happened to be in the docs. But they gave me a large number of names to choose from.
Next, I researched names I chose to make sure they were common within Native American communities in the US. Obviously, with intermarriage and all, pretty much any name is okay. But I wanted that subtlety that comes with just the right name. Just like my Jewish characters could be named Anthony and Catherine but are instead Joseph and Ruth.
This site is a general one but I found it helpful (after the rest of the research...names vary a lot by both tribe and region).
Your case is different from mine. You want names unadulterated by European contact.
I will urge you to pick your setting and tribe first. If you really can't, then do the research twice. Once for each of your top choices of tribe/location.
Use the historical documents you can find for that tribe. I don't know what is out there written by Americans. For the ones written by Europeans, there will be some that record actual names for the people they interacted with (as opposed to names given to them by the Europeans or nicknames used because they were easier to say). Make a list. Also use docs about tribes that lived close by and were friendly with the tribe you are using (close by doesn't always mean friendly but, if they were, then there would be intermarriage and names would transfer back and forth too).
Lastly, get a sensitivity reader. When you're all done with your research and have the tribe and names of your characters (with some extras), but before you're wedded to them, have an expert read what you've got to make sure it's plausible.