Where to keep that kind of data is obvious: use a database. How to keep it depends on a number of factors. Here are some use cases that come to mind:
Scenario 1: You only have to be able to reprint rendered combat messages
In this case, you could actually save strings in your database:
table combatmessages
id
combat_id
combatant_id
message
You can think of message as a cached version of an already rendered combat message. If reprinting rendered combat messages is all you want, this allows you to skip the rendering process, which makes data retrieval and processing very fast. The downside is that reprinting combat messages is really ALL you can do. (Unless you want to process the message, which would be insane.) Also, you have to store each message twice, for it reads differently for the two players involved in a battle.
Scenario 2: You want to access battle actions to calculate things
In this case, the structure of your database will be more complicated, for it has to represent combat action data, not just some lousy string. On the plus side, you can actually do interesting stuff with it. The design of your database will depend on what kind of stuff you want to do, and on how complex your battles are. If you are only talking about 500 or so players playing at the same time, I'd suggest to err on the side of flexibility and just store every bit of information that you can.
In order to store battle actions and events like the ones you posted, a table structure like this might suffice:
table battle
id
combatant1_id
combatant2_id
winner_id
combatant1_startHP (in order to be able to calculate remaining HPs in messages)
combatant2_startHP
table battlelog
id
battle_id
turn (if your combat system makes use of turns)
subject_id (null if there is no actor or receiver of this battle message,
e.g. if it's a global message to both combatants)
action_id (or action enum ('attack','backstab','missile'), if there is only
a limited, predefined set of possible actions.
null if the record stores an event that is not the direct result of an action)
target_id (null if there is no target)
resultHit enum('miss', 'hit', 'critical hit', null)
resultDamage int
resultWound bool (or enum if there are several types of wounds)
resultSkillImprovement_skill_id
resultSkillImprovement_points int
Note that storing combat data instead of rendered battle messages is also necessary if you want to be able to render battle messages in different ways, for example by using different message templates in different contexts. Another advantage is that you don't have to save battle messages twice anymore; one battlelog record provides enough information to render battlelog messages for both players.
Note also that this design is a trade-off between a simple table structure and easy data storage/retrieval on the one hand and high data efficiency and level of normalization on the other. If your game knows 200 different results of battle events, then storing 199 null values in each battlelog record would no longer be the preferred route to take.