It's a cool concept!
I'm not sure I'd categorize it as a "puzzle shooter"... the random damages of the bullets was never a huge issue, I just kept shooting when I had bullets, and then ran away until I reloaded.
I think it would be cool if, instead of a timer to reload, dice would appear on-screen that you'd have to pick up to reload. The dice would cycle between numbers, and you'd get the number of bullets listed on the dice. So it forces the player to think about enemy positioning more, and the timing of their movements.
I love the design of the main character!