Anything is possible: if you change enough bytes then you can change Street Fighter 2 into Super Mario World.
But seriously, KingMike is right: changing gameplay is usually tougher than changing graphics, and requires some assembly language knowledge. My rule with ROM hacking - as with many things in life - is that you should be interested in the journey, not the destination. In other words, if you hack ROMs because you want to hack ROMs, not because you want to do something specific to a specific game, then you're on the right track.
Then again, some of the things you mention there might not be so tricky. For example, decreasing damage from attacks might be straightforward: you find where your energy is stored in RAM, then when you get hit, you use a debugger to see what caused it to go down, and work your way from there. Assembly knowledge helps out there, of course.