It would be very cool if a bar and a line were added to the bottom-left corner of the screen (the bar is white in 3/4 of its length and the rest is green), and when the line reaches the green area then it means it's ok to shoot.
If it's too hard to do this (the line must to be syncronized with the beat), then maybe you should play a song with a more constant rhythm (an example of a game with a rhythm that seemed better to me was Patapon, there you had to beat the rhythm per second and it was easier).