The kosher (or kosher style) solution to this is a nice hard salami. You know, one of those wrinkled salamis that hang behind the counter at the deli. Actually, the way those are made is that the delis buy soft (fresh) salamis and hang them up for weeks until they dry.

As far as cheeses go, I have carried all sorts of cheeses for days or a couple of weeks at a time and none of them have every gone bad in any way.

Only problem I have with either of those foodstuffs is that they are pretty heavy for backpacking use.