Of course, long before there were dedicated toolsets, there was the humble game ROM. In addition to allowing people to finally brag about beating Ghosts N' Goblins, NES game ROMs had/have the added bonus of being fairly easy to manipulate. What better title to screw around with than the original Super Mario Bros.? It didn't have too many sprites and, oh yeah, there's that whole "pretty much defined video games for an entire generation" thing.
So the ROM-smiths went to work. It was simple stuff at first, like getting rid of Mario's mustache or even his clothes. Naked Italian plumbers soon gave way to stoned Italian plumbers. Most of the notable hacks of this early era were simple one-offs created for shock value, like Super Bud Brothers, which replaced some of the game's bushes and character sprites with weed leaves, and the disgusting Super KKK Brothers in which, well, you can probably guess its horrific gimmick.