I wasn't planning on actually replacing the textures inside the rom, rather I was going to use a plugin on an emulator to mask the textures.
Unfortunately, Luigi is only possible to replace with Mario since Luigi's images are larger than Mario's allowing for Mario's images to fit inside Luigi's image frame (translating Mario's images to line up properly would be necessary, but I didn't do this considering there is no reason since replacing Mario with Luigi won't be possible). Luigi on the other hand will not fit into Mario's image frame due to Luigi being larger than Mario.
Unless there is a way to allow larger images to replace smaller ones in texture masking with some other emulator plugin that I'm not aware of, then progressing any further won't be possible.
Since I did, however, take the time (about an hour) to create a demo texture pack to see how Mario and Luigi would line up on screen I went ahead and took some screenshots to let you see Luigi in action. Here you go: (You'll also be able to see what I mean about the image sizes)
Once clover's tool has come out, I'd be willing to bet replacing Mario and Luigi will be fairly easy to do, but for now we'll just have to wait.
On the other hand, Toad would be able to fit into Mario's image. Someone could definitely make a texture pack that replaces Mario with Toad. (The great thing about creating texture packs is once clover's tool is released you could potentially replace the textures within the rom with the ones from your texture pack)