Don't give up at all!
It's very easy to do. I'm using photoshop. but it should be about the same for every paint program that support alpha
1. Go in to channels, CTRL click the alpha map
2. Go bak to layers. Press CTRL + J, now you should have Guybrush on a separate layer
3. Paint the new hair, or what ever you wanna do
4. Go back to channels, paint alpha map black
5. Go back to layers
6. CTRL click on the Guybrush layer
7. Go back to channels, and fill the selection with WHITE
All that is white is gonna show in game, gray is 50% transparent.
I took my time to render your edit out, just to test it in-game. I'm uploading it as .png (with transparency) so you can use it if you didn't paint on transparency.
And it works like a charm in-game btw