ROM hacking as I described it would be just like that. If select a boy, you (well, the game's code actually) swap out every relevant sprite or background tile that draws the male character during runtime. If it's a girl, you do the same for the tiles that draw the female character during runtime. All you'd need to do is dynamically change is the address where the game looks for tile data depending on which choice the player makes at the beginning of the game, then the rest of the original game code handles everything else. Of course, you have to properly insert this tile data into the ROM (without breaking anything else) but that shouldn't be a problem.