For player p, let their score be S_p where
S_p = C_1 x w_1 + C_2 x w_2 + ... + C_n x w_n
where C_i = characteristic score i for the character (e.g. strength) and
where w_i is the weight of the characteristic
To normalize, it's probable easiest to have w_1 + w_2 + ... + w_n = 1
For a simple outcome simply compute the score for both players and compare - larger wins.
For something more complicated, you could do some sort of random draw to add a bit of randomness into the equation (i.e. the weaker one could be having a good day and visa-versa, allowing the weaker player to triumph).
To make the characters stronger, you simply increase their character scores. You can extend this as much as you'd like - if you really wanted, you could start randomizing the character scores a little (i.e. the character feels particularly strong that day), etc.
An example:
Say we're working of three characteristics, each weighted the same (1/3). PlayerA has scores: 10, 8, 20. PlayerB has scores: 11, 8, 4.
- S_A = 1/3 x (10 + 8 + 20) = 38/3
- S_B = 1/3 x (11 + 8 + 4) = 23/3
So using the simple scoring, PlayerA wins easily. Even with randomization, he's pretty sure to win against this PlayerB, but hopefully you get the idea.