Your premise is flawed, Native Americans do have representation in the Senate.
Any Native American that is a citizen of the United States has two senators that represent them in the Senate, based upon the state that they reside in.
Then there is the rather racist definition of "representation" which requires that someone of the same skin color, religious persuasion, etc. is their representative. Even under this definition, there have been several senators with significantly acknoledged Native American ancestry. Charles Curtis of Kansas 1906-1926, who later served as the Senate Republican Majority Leader (1925-1929). Robert Latham Owen, Jr. of Oklahoma 1907-1925.
Finally, perhaps you were just referring to Native Americans on Indian reservations requesting statehood.
The Senate of the United States shall be composed of two Senators from each state. U.S. Constitution, Article I, section 3, clause 1
There is some historical precedence for that. The Oklahoma Territory is composed of both Indian Territory and Oklahoma Territory when both were requesting statehood individually.
Representatives of the Five Civilized Tribes met in 1902 to work on securing statehood for Indian Territory and held a convention in Eufaula. [...] The convention drafted a constitution, drew up a plan of organization for the government, put together a map showing the counties to be established, and elected delegates to go to the United States Congress to petition for statehood. The convention's proposals were presented in a referendum in Indian Territory, in which they were overwhelmingly endorsed.
The delegation received a cool reception in Washington. Eastern politicians, fearing the admission of two more Western states, put pressure on the U.S. President, Theodore Roosevelt. He ruled that the Indian and Oklahoma Territories would be granted statehood only as a combined state.
So, in Oklahoma since 1907 Native Americans of the Five Civilized Tribes have had two senators representing them in the U.S. Senate.