The trouble with this sort of recommendation is that it would take a large-sample double-blind longitudinal study to generate even weak evidence that the proposal actually increases longevity, and performing such studies isn't remotely feasible.

This is simply not so. If specific studies show improved longevity from specific dietary changes, it is quite reasonable to infer combining multiple specific beneficiary changes will also result in a benefit.

Skepticism is warranted, but the idea that eating whatever you want is actually better for your longevity is just bogus.

There is no control group. The hypothetical diet/lifestyle of our evolutionary ancestors is the closest to a control, but it no longer exists.

You need to pick what experimental group you want to be in.

For instance, this 'paleo diet' business relies on the idea that eating the same thing our ancestors did in 10,000 BC will make us live longer.

Yes, because of a mountain of specific evidence which supports this hypothesis (omega 3, sodium, vitamin D, reduced calories, more fruits/veggies, etc etc)

But our ancestors lived much shorter lives than we do,

On average, yes. But based on what we know from hunter-gatherer tribes, a fraction probably lived to ripe old age, and these luckier/healthier specimens would tend to have more offspring. Regardless, just because we have eliminated most of their causes of death does not mean we have not also reduced our health in other ways.

we have only weak evidence about what they ate

Not really. We have reasonably good ideas about what they ate.

and anyway 600 generations is more than enough time for evolution to re-tune the human digestive system.

This is not a great length of evolutionary time, although it is enough for some strong selection effects for neotany changes such as prolonging lactase production and increased robustness for ceral grains. Nobody is saying that we don't have some neolithic adaptations - of course we do. But that doesn't mean they have had enough time to hit equilibria, or those equilibria are optimal for longevity.

Also, some of the more profound effects are far more recent, such as the omega 6 shift, artificial illumination, and sunblock which have occured in just a handful of generations - a blink of an eye.