[SCD]

Is there a gameshark code for Virtual Pro Wrestling 64 where you can change Giant Baba's shoes from red to black or is that something I have to do in hex editor? You can't change the color of his shoes in Edit Wrestler mode.

[FAST6191]

These sorts of cheats usually filter down quite well so if you have checked all the usual places and wrestling game hacker sites (they are not as numerous as megaman, mario or something but they do exist for certain titles, Fire Pro Wrestling being a good example) then you get to make it.
Watching http://www.youtube.com/watch?v=11xALjJBZF8 it looks like a texture spread across two jointed sections rather than any material colours (impressive attention to detail for an early N64 game). In and of itself that is not fatal to the wish for a gameshark but might trouble things; most such hacks you might see .

I would then learn to do it both ways- start with finding the texture in the ROM and then if it gets transferred to the RAM at some point then consider porting it to gameshark. I must confess I am not completely on top of the N64 3d systems so I do not know offhand if there is any unmapped stuff you can not touch with a GS.

[Zoinkity]

First, about the GS/AR:
Real-life GameSharks can alter any hardware address that's available.  Anything it can't do with basic codes can be forced by using codes to alter the codelist.  You can also circumvent the cache using uncached writes.  The only thing it can't do is write to read-only data, so you can't directly alter cartridge ROM (though you can intercept read requests).

Emulation is much more limited.  Unless you're using the slower interpreter mode you will not be able to alter ASM with GS codes.  Emulators convert ASM into PC machine code and cache it.  Although they catch when the game changes ASM, none seem to catch when a code does the same.  To use ASM cheats, you'd need to activate the code, take a savestate, then load that savestate.
It also doesn't emulate the GS itself, so certain hardware tricks no longer work.  Many don't implement the full range of codes either.

About what you're asking:
There is the chance you're incredibly lucky they might reuse the texture with a standardized external palette, because then you could just batch overwrite the palette with 0001's.  That's the way most 'customizable character' things are set up, but since shoes weren't an option you may not be that lucky. 

Otherwise, codes to do this would be complicated.  You would either need to change the display list at runtime to colorize the vertices black, overwhelming the texture; switch the image using one of several methods to a black one; if one of the pixels on the edge of the image is black, you might be able to change the loaded image properties to treat it as a 1x1 image; if it's a CI image (has a palette) you could batch overwrite the values to black (0001 or 000000FF, depending on mode); or change the combiner settings to completely ignore the image.

Sadly, that's not what's complicated.  What's complicated is that this sort of data isn't at a fixed address in rdram.  Dynamic allocation means this file is loaded to the next available space, with a pointer in a table to let the game look it up again.  That means you'd have to write an interceptor script with codes, a test to verify the file is the one you expected, then link the intercept via some other code to make the change.  That, I should add, is an ASM hack and therefore not emulator-friendly.
The other option is to make individual codes for every possible situation and activate the pertinent one when necessary.

Long story short:
Your best bet would be to directly edit the model or texture and create a ROM patch.

[SCD]

Is there a program where you can extract textures from a N64 rom and edit them in Photoshop and import them back to the N64 rom. This way I can edit other textures in this game.

[Zoinkity]

Yes and no.  I don't know of one that will handle every single different format.  I've had to code my own for different applications, and YUV is basically unsupported by anything.  In addition, you'll have to pipe textures through programs to convert 24/32bit color into 16bit color. 

Textures in these games are all compressed using that game's particular compression scheme.  Even when you do have the images, you'll basically have to rebuild ROMs if you can't get them to compress into as small or smaller a space.  That's the single biggest reason you don't see N64 patches very often.

So, really, you're going to need a tool specificly coded for this game.