My opinion: just use steel cans.
Steel has a 80%+ recycling rate, and even if thrown in the garbage... steel is one of the easiest materials to "mine" out of a garbage pit. Just shove everything into a blast furnace, and the things that don't burn is probably steel.
Obviously a bit simplified: but that's the secret to glass, aluminum, and steel recycling. The high-temperature "purification" process of these materials makes for a very easy recycling process, even if there are contaminants in the material. In contrast, paper and plastic becomes useless due to contamination very easily.
-------------
The amount of food available in steel cans is quite significant. Tuna, Salmon, Chicken, Peas, Carrots, Corn, Apricots, Peaches, Spinach, Pineapples, Beans, Potatoes, tomato paste... to name a few.
Subsisting on canned food is boring, but doable. You've got meats, every major veggie, starches and fruits. Mix it up with some grains (ex: Rice, Flour), fresh starches (Potatoes keep well and don't really need to be in a can), fresh veggies (Onions keep well).
---------
A combination of fresh fruits + cans manages to keep my trips to the grocery store down to once-per-week. Most fresh foods don't keep for a whole week (ex: Fresh Peppers, Fresh Basil, only stays good for a few days... while fresh ground beef / fresh chicken only stays for about 2 or 3 days).
----------
The counterargument to steel is that it is heavier than plastic. So it arguably takes more energy to ship steel cans than plastic containers. I haven't done the math however, but I assume steel is overall better for the environment.