Ok, get a photoshop and a wc3 image extractor<--From the site.
Now, open the image extractor and (for example) go to textures, Abomination. Left click on the abomination and save.
Now, open photoshop, open file, choose the abomination file. And start painting as you want.
Than save it, as TGA.
Now, for this proccess i think the best way is through the wc3viewer<-- Also download from the site.
So open the wc3viewer and press:convert BMP\TGA\JPG to BLP. open the file you want and save it as a blp.
Thats it, enjoy.