Can I include custom graphics for the Characters (not costumes just a graphic change)? I know thats completely useless but I just want to make sure

I think just not modifying the game would be safest if you are going to do runs.

In my setup I have replaced the default Toad with the Blue SMB3 Toad (that's also used in STTB). I have made a few Runs with it.

My take: If custom Character Sprites have an identical shape to the ones included in any of the permitted SMBX Versions and you can proof it, it should be allowed.

This is the Toad I am using now: Toad.zip

I verified that the shapes are identical by creating Mask-GIFs with the Moondust PNG2GIFs tool, and comparing their MD5 Checksums:

For character sprites that are shaped differently, that should be up to the Mod's discretion.