There's no *intrinsic* reason TOEs wouldn't be testable. If you want a story in which a TOE is more readily testable than is the case in real-world 2018, you just need to tweak some of the mundane practicalities that contribute to such difficulty here. Speaking as a physicist, a few examples off the top of my head include:

 - The fact that the energy scale at which "new physics" occurs is so many orders of magnitude larger than what our particle accelerators can access. Maybe in your world their design is more powerful, or certain physical ratios are smaller. The Planck length is determined by the strength of gravity, but you wouldn't even necessarily need a smaller gravity-electroweak strength gap, because the compactified dimensions in string theory can be much larger than the Planck length.
 - The fact that the TOEs present so many different options we can't narrow down. The string theory landscape is huge, but it's conceivable we could improve our search techniques. Just as *Silicon Valley* is about a team with a great compression algorithm, your story could feature an efficient landscape-searching algorithm that has shown all options consistent with past observations make certain predictions we can test elsewhere.
 - The fact that there's only so much we can measure. TOEs typically correct certain theoretical details of black hole thermodynamics. Can your civilisation measure black hole entropy? They might be spacefaring, or they might have worked out how to make miniature black holes they can study.
 - The fact that New Physics ideas have gone so long without turning up. Real data tell us that the proton lifetime, if finite, is much larger than early GUTs* imagined; real data also tell us that supersymmetric partner particle species, if they exist, have much more mass than the "standard" particles we know of. Again, your universe might not have these problems, at least not in the same degree. (* Grand Unification Theories still neglect gravity, but introduce a strong-electroweak unification.)
 - The fact that the real world is so much more complicated than early efforts hoped for. Kaluza-Klein might have panned out, if the nuclear forces didn't exist. (Large atoms' stability would then require negatively charged nucleons, but why not? It's your universe.) One downside would be that without radiometric decay you can't date fossils, but you might decide that's a small price to pay in your story.
 - Maybe your physicists have just been working at it longer. Every now and then someone proposes a more imaginative (and hopefully more practical) way to test a TOE than "get your accelerator to the Planck energy". Maybe in a century or two something will pan out. Bear in mind the theories are extremely young.