What you are looking for is: Adquedit
1. Extract it
2. Start it
3.a) Tell it your path to your favorite quake.exe
3.b) Tell it your path to your Quake palette (it is included if you do not have one)
4. Open the gfx.wad file that you want to edit
5. Browse through your gfx.wad file and find the textures you want to edit
6. Extract the textures you want to edit with the "export" button and modify them in your favorite texture editor. I use the .pcx format but there are others too.
You an even link to your favorite texture editor from within the tool and use the "edit" button if you want.
7. Once finished, use the "replace" button to bring them back into the gfx.wad
8. Close/save it.
Now pack your new gfx.wad into a .pak file and it will be loaded by every engine.
PS: Some screenshots with a brand new face texture (took me 1.5 hours till I was satisfied)