DC did a comic in the early 80's called Arak:Son of Thunder, about a Native American shaman who ended up at the court of Charlemagne and had all manner of sword/sorcery type adventurers.
I'm pretty sure Conan understood currency and prostitution, and he was still "the Barbarian." "Barbarian" is something other people call you, sometimes for no greater reason than what you eat or the way you bury your dead.
Your guy could be on a spirit quest in which he has to "walk the Earth." He could have been kidnapped by slavers. The Japanese fished the waters off the Pacific Northwest for centuries before Europeans landed, so perhaps your guy hitched a ride with them and made his way across Asia. Really, the possibilities are endless.