For the TMs, I do like the idea of Caldera gym leaders giving out TMs (and Venom Strike and Focus Sight being found randomly elsewhere) and Kirant gym leaders giving items. The Sedcini Rock gym leader, for instance, would be perfect for giving out Plain Stone.
As for competitiveness of Gym leaders, I like having coverage, but we don't need to optimize the TM with the Pokemon. Fernando's Phantern not being able to use Cherry Bomb well doesn't matter because Cherry Bomb is really freaking powerful for that point in the game. That's an 80 base power move in the third gym in the game. That's pretty insanely good considering that even Fahramane is probably using Ember at this point in time.
Backtracking is unfortunately inevitable with the cyclical nature of the region. You'll have to go through Icthyes and Cetacea then go back to Colossus to proceed to Dynamo Gardens.