As climberman said, Nadgee/Howe wilderness is a good region for such a trip, I walk in there a lot (every couple of weeks recently) as I live very near by. There is a lot of nosh about if you are adept at collecting/catching it and know what to look for and where to find it. I have begun
supplementing my trips in there recently without too many problems (I fish reasonably well and have a packraft to get around ...). I have just finished reading the excellent book
Natures's Larder, a field guide to the native food plants of the NSW South Coast by R J Hardwick.. It is a very handy book, and I will be taking it as a field guide on my next trip the week after next and hope to try a few bits and pieces. Take note of the warnings in this book, as what you are attempting is not for the inexperienced or ill equipped. That stretch of coast can be pretty extreme also, so I would be reluctant to attempt a self reliant trip in the middle of winter or summer when your energy (and water) requirements are higher. I spent 5 days down there this summer and really really struggled to find good water and temps were over 35oC.
Aboriginal elder Uncle Max Dulumunmun Harrison is a teacher of Yuin traditonal knowledge (including all the local bush tucker knowledge) and would be worth seeking out if you are really serious about understanding the bush and it's foods in the Yuin Nation.
The downside of collectiong bush tucker is that the really good stuff like fish, crays, shellfish etc generally requires 'equipment' to collect and that has to be carried...I have been getting a few of these lately (I take them home for my wife as I am allergic to them
)
Steve