What about a variant of the "sliding ice block" puzzle seen in some games? You push a block(or in this case, shoot a block) and it slides in a specific direction until it hits something. To make it make more sense in context, have it be some sort of mechanism where various gears or whatzits slide around on rails. The play picks which direction they slide by shooting them. The goal could be to get the gears or whatzits into specific places.
The problem is I don't know how well this sort of puzzle would randomize...it might require actually building a set of puzzles to seed in the game.
To steal another idea, another common puzzle is the "weight" or "volume" puzzle. The one where you have(for instance) a tank of water(or a set of weights, or a pressure gauge...) that needs to be at a certain level. You'd have three(ish) buttons that each add or subtract different amounts, and you'd have to find the combination that leads to the correct level.
Probably formulaic at its basic level, you might be able to randomize it somewhat without getting impossible puzzles.
Maybe a sort of memory puzzle? Have a set of objects which change state in some fashion(flashing, or changing color), and do so in sequence, and afterwards the player has to shoot them in the order of the sequence?
You'd have to be careful with this one, too few and it's trivially easy, too many and it'll just become a game of chance.
Oh, maybe some sort of Blackjack variation? The player is dealt "cards" by some mechanism, and then they can shoot buttons to either draw another or stop, and the goal is to hit some arbitrary number(though I guess 21 works too), or get as close as possible without going over.
...I probably didn't have to explain that last one.
Oh, speaking of things associated with gambling, what about some sort of "race" minigame? Not for the player, oh no, for monsters! The players bets on the monster they want to win, and they can help out by trying to shoot or otherwise slow down(but not kill!) the others. Races shouldn't be longer than about 20-30 seconds though, otherwise it might get tedious.
I think I deviated from the puzzle theme somewhere, but oh well.
Oh, what about a timing puzzle? Have a sequence of objects which flash or change color in a certain pattern. One might change color every 3/4 seconds, one every 1-2, one every 5 seconds...you get the idea. The object of the game is to shoot each object(one at a time, not all at once or even rapidly in sequence) when it switches to a given color, or flashes, or whatever. If the player hits it when it isn't flashing, the puzzle resets.