It is my understanding that there are whole industries set up to produce such documentation. Although I have not needed to avail myself of such realistic documents, I believe they are available for a rather pitiful sum of money. They can be purchased in any major city, especially if the city has a multinational population center.
Practically speaking, though, our cowpoke would have to first obtain the necessary funds to purchase the identity papers. Again, in any population center of note, he would observe many people who were living in conditions with which he was familiar. There would be a group of people (mostly men) huddled around a campfire (although the use of a steel barrel might be a surprise to him). These people, once they accepted his bona fides as a homeless drifter, would welcome him into their circle, and would be happy to direct him to the nearest shelter where he might obtain a hot meal.
He would be faced with the choice of either standing on a street corner with a sign, or he might offer himself out as a doer of odd jobs, for a small fee.
By carefully preserving his resources, he would be able to save the necessary funds to purchase the identity papers. I believe I have read that such papers can be had for as little as $100, although the higher-quality specimens may start at $500.
He probably would not want to claim his birth year as being in the 19th Century, though. He would be better served in purchasing documents indicating a birth in the latter half of the 20th Century.
The question would be whether or not he would know that he needed such documentation. It is fairly common knowledge now, but would be a completely foreign concept to a person from 1870.