You would need to hack the ROM for RBY. Pokemon is a very well documented Gameboy game, so experienced ROM hackers would not have much trouble. It's essentially hijacking the game (probably before the name input screen) then swapping every relevant sprite or background tile.
Having said that, you should look to http://www.romhacking.net/ as your key resource. The people there are very knowledgeable about this sort of thing. Just know that it would require you to get very familiar with the Gameboy. You'd have to understand its assembly language, how it draws graphics to the screen, how it handles input, interrupts, and all that stuff.
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.