It really depends on what you mean by off trail. Here in the US Northeast there’s no way you can go 3 MPH bushwacking in the mountains. On average you’ll do about 1 MPH, at worst you might be going .25 MPH. I think you guys are talking past each other because you the experience is vastly different depending on the terrain. There is no blanket statement about how far an average hiker can go in a day off trail.
As to the AT @ 40 miles per day, those folks are way on the extreme edge. Average time to hike the AT is 5 to 7 months, so much closer to 10-12 miles per day on average. And that includes several rest days and short mileage days due to weather, injury, or recovery. It can be done, but not by someone in reasonably good shape, but not an athlete as mentioned in the OP. Not to mention that 80% of those who start the AT each year drop out.
Some parts are trails. But many parts are cross country, marked by blazes. Just because the whole system is called a "trail’ it doesnt mean that most of it is a well trodden easy to hike trail.
And of course, you can follow game trails in areas with no introduced trails.
I’ll agree, it depends on the terrain. In some cases, one might find game trails that are the equivalent of a footpath; in other cases dense bush is almost impassable. There’s a reason canoes were the preferred travel method in the wilds of northern Canada.
And I’ll second those who say camping and hunting will slow you down. The natives of North America could for example, pack a few days supplies (and forgo eating if necessary) and move very fast when they knew the terrain and had a destination in mind, particularly a war party, all men. (Read something like Last of the Mohicans). However, as a tribal migration, they would move a lot slower. So the real question is, what did they eat and how much did they need to accumulate and carry? Pemmican is dried smoked meat mixed with dried berries. It was a native food specifically designed to be taken on longer trips (or stored for winter).
In many cases, wilderness would be surprisingly open, because the ground vegetation was choked out by trees. Some places would be pretty thick - but you wouldn’t travel through them casually. Certainly on flat terrain, 3 mph isn’t unrealistic.
I’m happy when I’m hiking, pack upon my back.
I’m happy when I’m hiking, off the beaten track.
Out in the open country, that’s the place for me
With a true Scouting friend to the journeys end,
Ten, twenty, thirty, forty, fifty miles a day.
Proof again I guess that the Girl/Boy Scouts lie in their music.
Wagon trains on the Santa Fe Trail traveled about 20 miles per day. There is a landmark called “The Tooth of Time” which meant you were seven days from the end of the journey (Santa Fe). It’s about 130 miles.
I’m not in great shape, over 25 lbs overweight, over 55 and have never jogged or did strenuous exercise or labor my entire life. I walked about 12 miles one day in 90 degree heat in Washington DC three summers ago. The day lasted about 14 hours and I stopped to eat ice cream, junk food from street vendors and did the tourist thing. Walking is pretty easy. My feet did hurt and couldn’t do it the next day, so I guess this disqualifies my answer.