I remember playing Super Mario RPG. In it when you are attacked you could reduce damage or even evade attacks all together depending on your ability to press specific buttons during enemy attacks.

That was fun - I recently bought the game in the Wii virtual store, and need to finish it. They refined and polished that mechanic even better in Paper Mario 64, and Paper Mario: The Thousand Year door. [video of combat] - anytime Bowser breaths fire, the "Nice!" is the player clicking the action button at the correct timing, to reduce damage. If he does it perfectly, it entirely blocks damage, IIRC.

Just a piece of thought; most turn-based games use one of two(or both) mechanics;

first is critical hits, which is basically the same mechanic as one-hit-killing or not, but balanced, usually such a game has ways of healing or even saving (critically) hit characters as well.(which is where the player-interaction comes in again)

Luck in a game is, btw, not just not a bad thing, if balanced out, it also gives randomness to a game, if you're going to make any kind of game that has even the slightest amount of replayability(or even better, some kind of multiplayer) you need to randomize things so the game doesn't behave the exact same way every time and becomes boring and predictable.(remember, there are often only a few objects(characters/items/buildings/fists) in a turn-based game that interact with each other.

The other is "type" meaning a fire-attack will do reduced damage against a water-creature for example; in FF tactics adv. the player got items that could diminish, negate or even absorb type-attacks, which meant that if an opponent did a fire-attack your character could get reduced damage(there were 2 levels of reduction iirc), no damage or even get healed. Pokemon is another example where creatures belonged to a type and could learn up to 4 different attacks which could all be of a different type.

I saw someone mention the quicktime event based dodge further up the thread. I was really impressed with the Gears of War approach to reloading (anyone unfamiliar, you are able (but not forced) to press the reload button a second time during the animation and if you time it correctly can reload faster with more powerful bullets. However, if you time it incorrectly reloading takes significantly longer).

This had an impression on me, simply because of the risk/reward element to such a commonplace and fundamental mechanic of the combat.

You could try swiping backwards on a character about to receive an attack to dodge, but if the input is not received within a window the character takes increased damage for the hit. This would also allow enemies to make feints and appear to attack one enemy but instead attack another at the last moment.

(On a personal note, I had purchased Bushido Blade when I was quite young and it had stuck in my minds for years without me able to recollect it's name. Thanks for the reminder!)

Another idea:

What if each character/unit/player/whatever had an "evasion" score. Either an attack value would have to surpass evasion in order to be successful, or if you kept random chance the percentages could be modified based on the evasion score.

Every move chosen would also have an evasion modifier. Say for example that possible evasion scores are from 1 to 20. You might choose to perform an "evade" action, which is otherwise useless but boosts your evasion score to the maximum value of 20, but if you instead choose to attack you might choose a weaker attack that provides a higher evade value (say 15) or an average attack that provides an average evade value (say +10), or if you're really confident you might choose an absolutely devastating attack that modifies your evade value negatively (-10). You then have a balancing act where you can still choose any attack, but want to try to keep your evasion score high unless you're sure it won't matter.

I think this is the right idea. Couple the "evasion" score with a "hit" score and the battle would consist of constantly manipulating the two scores so that you're evasion is higher than the opponents hit score and vise versa.