I think the idea has merit. We must acknowledge that all turn-based games rely on having at least some randomness to keep things dynamic and prevent combats becoming trite solved puzzles. This is regularly done with random party/enemy placements, accuracy, damage, terrain generation, etc. So let's say we want to add another dimension to how dynamic our combats can be by forcing the player to account and compensate for variability in movement across the grid.
First things first... disrupting a pillar of tactical combat by making base movement speed random is going to create a lot of problems: it'll fuck with established design tactics and rules, meaning it'll have a much bigger overall design cost, and it'll fuck with player expectations, leading to frustrating unexpected outcomes. So instead, I suggest keeping base movespeed across the grid a fixed number between 1-5 squares per turn, depending on things like stats, class, perks, equipment, etc. For this example I'm going to use a rectangular grid, I guess.
So at base, you get to move 3 squares per turn, every turn. You also get a free "teleport" action every turn which allows you to pick any point within 12 squares of the currently selected character, and appear somewhere within 4 squares of your chosen point. We can then add in a requirement for the player to rely on additional movement options, by having huge maps or difficult (even impassable) terrain, ranged enemies that must be closed with quickly, etc. The player will naturally realize the necessity of relying on more powerful, but also more random movement options. This adds a new dynamic tactical element with a risk-benefit trade off. I will note that TOME4 has teleports of this nature, but does not really design around them.
Let's come up with a basic design around this concept. Instead of "Teleporting", you are "Tunneling". This is now a Dwarf rpg. Your party of Dwarves each pilot a different class of Mole-Mech. Each Mole-mech can only move 2-4 squares per turn (depending on class or equipment), but all of them can do a free Tunneling action to move 10 squares quickly and blindly, coming up within 3 squares of their chosen point. Mechs can tunnel once every 0.5-2 turns based on their class/perks/equipment. The player will be forced to use Tunneling in order to traverse the grid more quickly, breach difficult terrain, scout, interrupt enemy movents and formations, and so on. Some mechs create terrain or damage effects at the point of entry/exit/between, some stay underground until the end of the turn and repair before emerging, some skip the randomness and home in with exact precision to the location they want, and so on. We have achieved our goal of introducing randomness in movement without disrupting existing designs, adding a new dynamic tactical lever, more options for the player, more options for the designer. It's a great idea to build a game around.