To my, admittedly limited, knowledge in the area, there is absolutely no evidence of pre-historic exercise regimes. You must remember that almost all the evidence for cultures that far back is based on archaeological evidence, and most often on tools and objects of a practical nature - when the written word was developed it grew the information we could receive from the past exponentially.

That said, hunter-gathering cultures still exist in the modern world, especially localised in SE Asia (such as the Aeta people of the Philippines, and Angu of Papua New Guinea), the Arctic (the Alaskan Yupik people), and Africa (including the Mbuti, and Efè). You'd probably have more luck researching their observable routines and considering its relation to historical cultures (which is something historians actually do - there's only so far you can go with pottery sherds...)

For more modern cultures, that's far more extensively documented. If you were in a Greco-Roman gymnasium I am almost certain that, if you were moderately well versed in exercise, you would be right at home. The Roman bathhouse was an odd combination of swimming pool, spa, social center, and exercise grounds, used by almost all members of Roman society, both men and women (different times though, there are limits!). Probably the biggest culture shock is in the name; Gym from Gymnos, meaning naked. But everyone is nude, so it's all good, right?

The current lockdown due to Covid 19 probably gives a pretty good insight into historic exercise - you work with what you've got without all the fancy gym equipment and whole line of sequential weights. The Greek sophist (type of teacher) Philostratus wrote about athletes running, swimming, weight lifting, pulling heavy plows, boxing with padded bags, horse racing, and a whole lot of wrestling. Greco-Roman wrestling was incredibly popular - it coined the expression "it's all fun and games until someone loses an eye" because literally the only rule was no eye gouging. Throwing sand in the eyes? Check. Throttling? Check. Scrotum grabbing? Check. Eye gouging. Not acceptable.

Here's Philostratus' text, if you're interested https://www.loebclassics.com/view/LCL521/2014/volume.xml

As for Roman gladiators, similar in training to soldiers, but a very interesting detail is that their diet was highly regulated. They ate a whole lot of barley. To such a degree that a name for a gladiator was "hordearii" - or a "barley-man". They were otherwise largely vegetarian (so much for paelo nonsense) and would take calcium supplements in the form a kind of disgusting sounding crush bone/ash broth. The idea for gladiators is that they would have a whole lot of muscle, but also a nice layer of fat over it (like most strong men these days - they definitely don't look sculpted), the idea being that any cuts in the arena would be incredibly bloody and look good to the crowd, but the damage would be to the fat, not the muscle, and thereby not overly damage the very expensive (to the owner) sporting goods. Rather macabre, but this is Rome.

Militarily, well, that's a whole other story, and I could write a whole lot on it. So I'll give the short version - yes, the Roman professional, post-Marian army put soldiers through the ringer, as you say, and they trained extensively carrying full gear and armour. I believe the average march was about 25-30 miles a day. Training for marches was something like 20 miles in about 6 hours (five Roman summers - but roman hours are... weird. There are always 12 day and 12 night hours, but with summer and winter having longer days/shorter nights, the hours can be anything from 45 modern minutes, 1.5 modern hours); they would carry about 22.5kg of gear on the march. Repeated slow marchers could potentially be beaten with cudgels, sometimes to death (known as fustuarium)

The shields they trained with weighed twice as much as the actual shields they would use to build arm strength. Roman oblong shields, scutum, are not lashed onto the forearm as commonly seen in movies, and other cultures - they're held by a horizontal bar inside the boss. IIRC they weigh about 10kg. The original armies of Rome were citizen soldiery, and they were provided a specific training ground to the south west of Rome, on the other side of the Tiber River, an area of swampy ground called the Campus Martius, or Fields of Mars (the war god). This was later built over as Rome expanded towards the end of the Republic, but prior to this was the defacto staging area of the army, and military training ground (a returning Roman army could not enter the sacred boundary of the city, the pomerium, without invite from the senate, and would wait at the Campus Martius for said invitation. As the Roman army became more a profession than a citizen army, the practices would have move from the Campus Martius to various forts and and military bases where the legions were stationed, though raw recruits were generally trained for up to six months before being placed directly into the legion they were part of.

I'm afraid I don't know the specifics of Greek milita forces, but I imagine that they were very similar to Roman ones in terms of practicing drills and formations on a somewhat regular basis when more important things like actually tending crops weren't more pressing. And this is really the point to take away from this; most of history, the vast majority of history, has been a struggle for subsistence and survival - working day in an day out to feed oneself and ones family, often barely above the level of malnutrition or starvation. The very lowest classes would have had physically hard enough lives with manual labour, never mind hitting the gym for a few naked laps with their old pal Perioceles the Ripped.