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.
Try a knife and a firelighting kit.
No self respecting " Aboriginal" stires out of doors without them. They leave that sort of nonsense to so called "civilised" people.