I love the idea of finding a name to honor your Apache & Cherokee heritage. If you are not familiar with names from these groups, then perhaps you can find someone else who is part of the cultural group who can advise you. Otherwise, perhaps you could use a place name that links to your heritage. (Many place names in the US are derived from Native American languages.)
However, I also think [name]Bina[/name] is fine as a full name. We have [name]Tina[/name], [name]Mina[/name], [name]Nina[/name], so why not [name]Bina[/name]?
It seems like you might be looking for more of an international name? You might look for English words/names that are somehow derived from the Cherokee or Apache languages. For example, I believe the [name]Sequoia[/name] (name of tree in English) comes from a Cherokee name that means ‘sparrow’.