Use Foraging, along with "Region Lore" (i.e. Lore: General (region xx).
The Lore provides the knowledge, the Foraging skill itself provides the act of find food, water, and with a tiny stretch, even shelter.
The other skills you list could also be useful in certain situations.