The answer provided by Grzegorz Sławecki is already a good one, but I wanted to explain the rationale behind his method and give you the tools to adapt the solutions to your gameplay needs.
The parameters of the present problem are the player's attack level a, weapon damage w, the total inflicted damage in one attack d, the enemy's health H and the minimum number of hits necessary to kill the enemy, let's call it n.
If you want the player to kill in n hits, then his total damage d must be such that
(n-1).d < H ≤ n.d or in other words, n = ceil(H/d).
d depends on weapon damage w and on the player's attack level a and we can expect weapons to get better as the level increases, so let's write d(a) and w(a) instead of simply d and w. The enemies the player faces are also expected to get tougher so, again, H(a). These are all increasing functions of a, and you want them to satisfy the above inequations. The unknowns of the problem are functions. You set one as a constraint, and you find the others. You do have degrees of freedom though, which is a good thing.
If I understand your question well, you have a precise gameplay in mind, and this gameplay is mainly represented here by the number of hits required to kill the enemy, n(a). Therefore, set n(a) depending on the gameplay you envision for the game and then find the rest of the variables of the problem. This is what you should always do because, as your question shows, your first attempt was to try an algorithm you thought may do and then realized it resulted in undesired gameplay.
Let's suppose, for instance, that you want the player to have to hit more and more times as he progresses in the game. You also want that, as the required number of hits increases, it increases less and less often, so that the player spends a longer part of the game hitting 5 times than 2 times. Here's what n(a) looks like:
The function used is n(a) = ceil( 2/3.sqrt(a) ).
We want H(a)/d(a) to stay within the ranges of values that make n(a) have the desired value and since n(a) = ceil(H(a)/d(a)), these ranges are the following rectangles:
and H(a)/d(a) can naturally be set to 2/3.sqrt(a) so that we get the following graph, with the red curve being H(a)/d(a):
Remark: we can easily find H(a)/d(a) here because we know the function of which n(a) is the ceil, but if our specification for n was less nice, we'd have to make our own fitting function using various tricks. Not all problems are this nice!
So we want H(a)/d(a) to resemble a customized square root function and we know that H and d must be increasing functions. Solutions are aplenty. For example,
H(a) = a . 2/3.sqrt(a) and d(a) = a
But we'd like the damage and the enemy's HP to increase an awful lot so that there are big, impressive numbers at the end of the game, just for style, so we instead set
H(a) = a² . 20/3.sqrt(a) and d(a) = 10.a²
The whole point, and the best part, is this: you know that your solutions to the problem (H(a) and d(a)) obey the specifications (n(a)), so you get the same n(a), but you have freedom. You know exactly the freedom you have, and you can use it to customize the experience. You should always try to give yourself such freedom while satisfying your most important needs, whenever possible.
Now that we've chosen the one-hit damage d(a), and since d(a) depends on the weapon damage w(a), we can use d(a) as our specification and try to find a w(a) that gives us this d(a). The principles are the same, the problem is different: we want the player to cause more damage as his level increases, even with the weapon remaining the same, and we also want the damage to increase when the weapon alone gets better and the level stays the same.
But what importance should each factor have? Suppose we want level to be more important than weapons: a bigger part of the variations of d(a) = a² should be independent from w(a), for example with
w(a) = 22.sqrt(a) and, therefore, d(a) = ( 22.sqrt(a) ) . ( 10/22.a.sqrt(a) ) = w(a).( 10/22.a.sqrt(a) )
We get the following graph for w(a)...
...and still the same d(a), because we again found a solution that obeyed the specification, here d(a), and we do have the properties mentioned above with w and a contributing to the damage (suppose we look at d as a function of a and w: then if a were fixed and we had w vary in the equation d(a,w) = a/30.w, d would still be an increasing function of w, and the same is true if you fix w and make a vary).
This w(a) could give you the value to be displayed in the weapon's ingame description: we would get "Weapon Damage : 220" with the best weapon in the game for instance.
We could have used a completely different specification for our gameplay and therefore for n(a), for example one that makes the number of required hits increase quickly as the game progresses and then plateau, and the resulting solutions would have been different.