A shade brighter on the brown would be better since it now blends with the background.
I think something like this would be optimal but I guess it's not doable without multiple sprites like in the mega man games or batman: rotj.
That's a pretty darn good mockup!
Unfortunately, you are correct.
We are currently limited to 3 main colors for Link, which are brown, green and beige.
4th colour is used for transparency, sadly.
The only way to achieve your mockup would be to do a mask sprite ala Megama indeed.
Also for the brown being TOO dark...
That's the only other shade of brown below the one used by default.
You can check here, this is the whole colour palette the NES uses:
Link uses colours 18 for brown, 2A for green and 36 for beige in vanilla Zelda II.
I changed them to 08 brown, 1A or 19 green and 37 beige.
I'm tempted to use color 07 instead of the brown, but not sure how well received that'd be.