Since I'm the kind of person who can live for a long time on "cold cuts," I'd recommend them - especially if you can stock up on better quality ones. HB eggs. Veggies. Just as you can find small restaurants in almost any town, you can almost always find grocery stores. Be creative - if you see a sign for something like, "Boiled crawfish - $3/lb," on some stretch of road, change your plans for that night and pick some up.
You also asked about storage. Baggies/ziploc bags will leak if the ice melts too much. Plastic containers with screw-on lids work better. But your best bet is to make sure to empty the cooler and get new ice in it every night when you pull off the road to sleep. The only problem I had with food getting wet was the night I was so exhausted that I pretty much just fell into bed. Stuff was floating a bit the next morning.
"Right is right, even if no one is doing it; wrong is wrong, even if everyone is doing it." - St. Augustine