Charles Bronson would need to be skinned for this also, he often played as either a gunslinger, Indian or Mexican.
Also look up Danny Trejo, he'd make an awesome bandit.
I don't really see why you would have to be overly realistic with the time period. You should mix it up a bit. Have it set during the golden age, but still have renegade Indian bands etc Geronimo and his band of renegades were active up until 1886.