Hmm, one doesn't see aboriginals often with footwear, but they always have a blade of some sort.

Then there's Cody Lundin. While he's part of the long-haired hippie freak crowd, he does make a point that shoes in the wild are essentially unnecessary. He too always has a knife.

In a clothing optional situation, I'd say buttflap takes precedence over shoes.