Good luck with the food issue. It sounds like a really cool adventure.

For fuel on a 4 week excursion you might consider a collapsible wood burning stove like the Emberlit Ti. The fuel is free and picked up along the way. However I really like the Trangia stoves too and find them very versatile.

I love going into the unknown like that. Who knows what will be available and when or how much. Perhaps a bit of foraging for nutritious greens might be possible. I keep a few kindle reference books for specific areas on my phone.

If you do a write up of this trip post it up here. That will be very interesting.