I think the big question is, how do you feel about armor? If your concept is little or no armor, you could even start with a warrior monk. The Self Control skill category is full of skills for pushing yourself in heroic ways: frenzy, adrenal strength, etc. Don't let yourself get stuck thinking of those as meditative discipline, it could be coming out of rage or determination, that's a character choice that's really irrelevant for the game mechanics.
If you want light to medium armor, rogues aren't bad for the outdoors. And of course fighter.
SoHK has the barbarian which is obviously what you are looking for. It also has the outrider which is like a thief with less of the social/urban and more outdoors skills. Less Conan but could be a perfect fit for some other members of the tribe.