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.

A game I played had a defend mechansim where a character could defend instead of attacking. This would skip your chance to attack, but would reduce the damage done to said character. This was especially interesting when battling ranged units.

I didn't read all the other comments, so I might be repeating something. But with SillyCow's comment as a basis, here what I feel:

Imagine a game where, in your own turn, you attack and the opponent can defend. Vice versa in his turn. Depending on what you choose to defend and how you defend against it, that will affect how you can counterattack him in your next turn. This way, you will get a turn-based game that is also, to some lesser extent, reactive and immediate.

Consider a turn-based card game such as Magic: The Gathering. The entities are cards but the principles are very much the same. You have the ability to play certain moves at certain phases of either your turn or the opponents. Depending on what you specifically play, this can have consequences (either good or bad) for any of the subsequent turns. On one hand, you might play a powerful Wrath of God or Armageddon spell that kills all in-game creatures or lands respectively, including your own. On the other hand, you might want to place that extra Land or other ability that either gradually (over time) or instantly (after a countdown) makes you stronger.

Now try implementing these mechanics into a turn-based fighting game between 2 Bushi. No armies, no lands, just the Bushi/Samurai in a turn-based version of Street Fighter or Mortal Kombat. Instead of creatures, you could have Chi buffs in soft spots that the opponent could try to attack with his moves. Instead of Lands, you could have Mindlessness or similar that over time gives you a greater ability to recall the various sword moves that you've learned thus far. The sword and other attack moves would be the equivalent to the spells in MtG. And so on.

Shouldn't be too hard.

You could take a look at Waving hands / Spellcaster / Warlocks / Firetop Mountain for a turn based entierly non random battle mechanic thats pretty neat.

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.

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.