Quake may only have a palette of 256 colors, but you can mix those colors to make new ones by checkering two existing colors. Change to the paint brush/pencil, make it as small as it goes, one pixel wide, and just do the checkerboard pattern using two colors mixed. To make very interesting effects you'll be doing it for a good while, but that's part of the process.
In the example on the top right you'll see a purple made from the two Quake palette colors. A rich purple is one of the missing colors that's always annoyed me, but you can make one simply by mixing two or more of the violet and blue colors which are available. On the bottom right ther is a zoom in on a section of that purple showing the colors I used in this case.
And be aware this is also a good way to make subtle shadows. Check out the original base skin under a high zoom and you'll see how this simple effect works.
Quake is a 3D environment. It creates a number of shadows on your player as he moves around in the map. But it is a very good idea to make shadows on the 2D image to enhance the 3D effect. Things like a subtle darkening under the arms and on the sides of the stomach really go a long way when you see the guy in the game.
And the other very cool thing is we naturally see depth in dark and move lighter areas toward us, mentally. You can create visual effects that appear to exist even though the player is relatively flat even in the game. Like a raised collar around the neck, a jacket over a shirt underneath, or really anything. Simply make the dark areas on the 2D to represent the depth as you would normally. When they are placed on the 3D player model it will appear to be more 3D than it actually is even in Quake.
In the examples on the left you'll see a really obvious use of this effect. This is a gun I did that has kind of a "cross" look to it when you're looking down for the top. The gun is of course just as flat as ever, and from the right angle it's very clear that it's still flat on the frame. BUT in play, as the guy runs around and you only see what you can as he moves, it looks very real and appears to have these two 3D branches on the sides.
Distortion can screw up your guy pretty fast and make him appear very different in the game. Don't make skins for pretty to hang on your wall. If you're going to do that you shouldn't bother using the skin pattern and palette anyway. It has to be playable and you'll need to take the stretching issues into account and change your guy if need be to compensate. The edges of the front and back are the most important to consider. As the front and the back are stitched together some details of you skin may disappear in 3D if they happen to be in a stretched location. Test it, and not just in qME; play the skin.
Get the skin in a game and look at it. Find a friend and have him wear it so you can see it. See how it looks in motion, in the dark, and in the heat of battle. Get a feel for the skin and be sure you are happy. "Finishing" the skin too early will just mean you have all these "versions" you're trying to pass out every couple days. It's lame and makes large collections of half finished trashy skins (like what you find in a lot of the packs). Try to get it positively right before you release it. I'm certainly bad about that; I wish I had more time to finish skins up. But at the most I try to only have one major fix for a skin if there are more things that need to be done. This allows me to "get away" from it for a little while and have a better feel for finishing my vision's intent when I return to it.