If you can't think of any way to make an RPG hard except to randomly introduce RNG based mechanics, you are not a good game designer. There are tons of games out there which feature difficult and killer battles without using RNG based techniques.

Hell, that's the entire reason Dark Souls has been as popular as it is: Because it is fair in how it kills you. There are tons of other examples in games too. Shin Megami Tensei usually only instantly kills you if you screw up a battle. Yes, it may kill you several times as you learn the rules (as you said, a learning experience), but it doesn't just pull a Yiazmat and say "sorry, I rolled a 100, you're dead, restart". Bravely Default is another fantastic example of difficult but fair combat in an extremely traditional JRPG setup.

Games can be hard, and can result in Game Over screens. But they shouldn't be cheap or unfair.

Next time you reach the end boss of a game, roll a d100. When you roll a 72, you can proceed to fight it. Let me know how long it takes you to give up and just play on.