Directly east of the Mississippi is the Shawnee National Forest in Southern Illinois (https://www.fs.usda.gov/shawnee) with 289,000 acres with both primitive (free but 14 days max per camp spot) and dispersed camping allowed.

I grew up in the area and camped many times with friends in high school and college by just walking a few miles down a trail and then moving off the trail a bit. I believe back then the primitive camping limit was 90 days per spot. The Rainbow People used to push that to the max when they moved through the area.

I live in New England now and other than some remote state parks here in Massachusetts there isn't any primitive camping so you are right about far east of the Mississippi.