Very cool idea.
I think a good choice would be to lower the health of the enemies. I think that would pivot the game into more of an attrition challenge (a la darkest dungeon), instead of having all encounters be life-or-death. The main thing this would solve is the tediousness of waiting through combat.
As you mention yourself, the balance is off due to the large randomness. If you made the game with only d4's (and maybe d6's, rarely), the player would have a much better sense of their own power level, and the impact of adding a die, and it would also lower the randomness and hopefully fix the balance a little.
But again, really good idea!