When you're fighting that strong boss and you're low on health and items, you so intently watch how much damage you're going to deal - you wish for a high damage.
The amount of damage you deal in a situation like this makes you feel one of several ways: satisfied, frustrated, amused, incredulous etc. In any case, it's something that made you get involved in the game, get immersed. Damage-variance is responsible for this, for this "roulette" flavor of entertainment.
Like others have said, using damage-variance doesn't greatly affect the outcome of the battle or take away any strategies a player might have: a stronger unit will always deal more damage than a weaker unit, even within a damage-variance model.
You address this matter with the concept of base damage, or minimum damage; The lowest damage a unit can possibly deal in an attack. What is determined by chance is the 'bonus damage', a value ranging from zero to a defined amount that is added to the base damage.
If you make a graphic of the base damages and bonus damages in your game, you'll see that these ranges follow the "skill" of each unit.
Skilled units have higher base damages than inexperienced units.
To make things more interesting you can play around with variances: the more experienced a unit is, the more "reliable" it becomes - it deals a lot of base damage and has little variance. Inexperienced units deal less base damage, but have a bigger variance.
This can also be implemented with attack types: different attacks have different base damages and variances.
Mind you can still make some types of attack like magical or weapon-based still be deterministic, even within this damage-variance model. An attack type with a fixed amount of damage is a weapon with 'zero bonus damage' (zero variance), dealing only base damage.