If he was born in Muskogee, Oklahoma and his mother was Native American. then Its a good chance he was of Creek Indian descent, and if he was born around 1900. Then its also a good chance that he was on the Dawes Rolls. He would have been around 5 to 7 years old, because the rolls closed in 1907. I would check the Oklahoma historical society Dawes Rolls website, and check the freedmen and by blood rolls.
Did he marry in Muskogee, Oklahoma? if so, then you can call the Muskogee county court house and check to see if he has a marriage record down there that would provide you with more family information. Did he have any sibling? Is that his real first and last name that you gave?