There can be no non-gimck difficulty it a turn based game? That is absurd.

If I were to match you up against one of the super chess computers it would indeed be extremely difficult, there would be no gimcks employed. In this case the difficult would lie in out thinking an extremely intelligent AI. Extrapolate chess to something like FFT, or any other turn based RPG. So it is indeed possible.

If you were to face an exact copy of your party in a turn based game it would come down to who could be smarter about their moves, and if the AI is good then it becomes difficult.