And back on the topic, I'm now leaning towards resigning myself to accept dice rolls. I just don't know how I'd solve certain problems without them.
As Kseh pointed out, you can do without dice rolls if you know what output there will be on a situation the player may find himself in, but that's exactly what I don't want to know. I'm not making a linear story. I'm making an open story where the player may choose to flee from a fight, or stalk the prey in the dark while strategizing how to attack. Or even where the player may not notice he's being stalked, or if he does, he may get a chance to successfully hide.
This leads me to have to consider that the player must have a chance to fail as well as succeed in many different situations, not just combat.
I was thinking about what displeased me most about dice rolls in Oblivion and Skyrim: pickpocketing. And I realized why it displeases me, it's not really the "luck" factor, but the lack of nuance in the failure state. If that makes sense. For example, when you fail to pickpocket, you just ruined the game. The NPCs will be hostile to you and fight to the death because of a cheap ring. That will get all the guards on your butt, and you'll either go to jail or further increase your bounty. But even if you do time in jail and make everything go back to normal... you probably murdered an NPC already, and you might not want to. There's no chance to apologize and give the ring back, and to try to calm down the NPC, and maybe even make up for it and gain the NPCs trust back. There's also no such thing as a non-suicidal NPC...
That's usually the problem that needs solving, and after having realized that, dice rolls don't sound so bad now.
Another problem I always had was missed blows in old RPGs in the style of Baldurs Gate. The characters simply missed too much, making them seem like they were inept fighters that couldn't hit a cow in a corridor. I think this can be solved by not having such low probabilities of hitting, and better excused (or justified) if the enemy has a high agility and probability of dodging, which might be countered by the character's perspicacity, which might still not be enough to compensate for the enemy's reflexes, and so on through as many possibilities I'd put into it.
I also think this can all be translated into text in a nice fashion, as well, making combat interesting to read and fun to play (kind of like DF, but not quite as complicated in the numbers).
So, unless someone has a great idea on how to do all this and have unpredictability without dice rolls, I'm probably going to resign to using them.
Once again, thanks everyone for the great feedback.