Yes, it's possible. It's not too hard to change the graphic data, the NES has a separate ROM chip in the cartridge for the graphic tiles, so getting into that table and changing it is easy. Manipulating the way the game works is a lot harder though. I've done some basic graphic tinkering in games, just because I was bored, but never did anything indepth. There's a lot of information out there on the 'net as to how to do it though.
-Ian