Some people may find this to be useful as they want Link to be a different colour. This is just a quick little starter tutorial and isn't complete. The addresses in this tutorial are those of the main palettes and does not include every palette. What does this mean? It means that not all of Link's palettes will change in game and you will have to search for values yourself (It is not difficult at all).
To do this you will need a hex editor and a brain.
Link's various sprite values are stored in bank 13 (0x4C000). Usually there will be about 4/5 bytes per part of Link (this includes all forms of Link whether it is slashing a sword, standing still, jumping, etc). These bytes include things like the position offset of that part of Link's sprite and the palette. Should you want to get in depth and edit the position offsets just fool around with the values you see. You won't break the game, I promise.
So here is a quick list of most of the main palette addresses for Link:
0x4Cxxx
*Left side and Right side denotes which half of Link the value corresponds to. Link is not one sprite block and has a left half and a right half.
004 - Left side standing palette
008 - Right side standing palette
00D - Left side, left facing palette
011 - Right side, left facing palette
016 - Left side, jumping right palette
01A - Right side, jumping right palette
01F - Left side, jumping left palette
023 - Right side, jumping left palette
028 - Left side, pushing down/up palette
02C - Right side, pushing down/up palette
031 - Left side, jumping palette
035 - Right side, jumping palette
03A - Tiny spinning/falling palette
044 - Left side, up sword palette
048 - Right side, up sword palette
04D - Left side, right sword palette
051 - Right side, right sword palette
056 - Left side, down sword palette
05A - Right side, down sword palette
05F - Left side, left sword palette
063 - Right side, left sword palette
068 - Left side, up bracelet palette
06C - Right side, up bracelet palette
071 - Left side, right bracelete palette
075 - Right side, right bracelet palette
07A - Left side, down bracelet palette
07E - Right side, down bracelet palette
084 - Left side, left bracelet palette
088 - Right side, left bracelet palette
All of the values listed will edit Link's palette for when he pushes and object, picks up and object, jumps with a feather or off a cliff, stands still, moves around normally, uses his sword or shield and falls down a hole. Perhaps a few more things change but those are the main ones.
Now to actually change the palette. To change the palette you only need to worry about the second nybble (second value of the byte, eg. 0x40, 0 is the second nybble/value). You will encounter values such as 00, 20, 40 or 60, perhaps others as well. The value 0 represents the green palette that is normally used by Link in game. 01 is a blue palette, 02 is a red palette and 03 is a yellow palette. You can experiment with other values yourself.
Since there is a nice 4/5 byte, sometimes 6 per part of Link and you are most likely over the age of 10 and have learned of patterns, I have faith that you can find the rest of the palette values yourself. Good luck!
