Hmm, well if you make trees destructible, there could be a new indestructible piece, presumably a wall or a rock. (Though I realize 8 shots is practically indestructible in most cases.)
You could have more than one kind of gate key, but that can lead to lazy level design. (Go get this key, go get that key... isn't necessarily fun)
A new type of weapon might be fun though, preferably something that worked quite differently, like a bomb.
I remember when I first played this game I was initially disappointed that the standard ([A]) shot didn't kill anything, so there could be some sort of weak enemy it could kill, but whether that would really add anything to the game is somewhat doubtful.
Some type of enemy that shoots diagonal might make for some interesting possibilities.
How about an enemy that moved continually, but in a predictable way. (Giant beatle?) For example if it always traveled in a straight path until it hit something, then turned right. This could lead to tricks like opening a gate to let it get out of your way, or leading a spider into its path to redirect it.