Actually, you can use the old skin as a base. You however have to add high frequency data to take advantage of the extra size. Basically all textures are bilinearly filtered in wc3 (you could try forcing trilinear with some drivers but it might not work too well so any sort of normal resize would be out without manual details being added.
Some computer filters can however add high frequency edge data via edge detection and other complex algerthims. Yes this means that stones might have noticably better edges on a wall (thiner, less blury), but this is still data extracted and estimated from a lower resolution texture. This method can not truely be used to improve texture detail and will not justify 4* the storage requirements..
Thus to create a high resolution texture you would firstly need to resize the base texture to twice in both demensions and in doing so use a filter which will give you the best base to work on (probably normal bicubic and such). You then will need to use your pure artistic skill to add a lot of fine detail that is a higher frequency than the base image. In the end you will probably find your using the orignal as nothing more than a guide due to the ammount of repainting. Additionally the higher frequency support might not suite the model design and as such you will have to actually change the skin art in some cases.
All in all WC3 is not suited for higher resolution textures, as it does not even use trilinear filtering for crying out loud.
I would however recommend trying this in SC2. It would be a great artistic experiment to bring a WC3 model up to SC2 quality. It would not violate the game port rules purly due to the ammount of work that would need to be done inorder for it to fit in.
Firstly you would need to enhance the model, adding 50-100% more geometry (do not think SC2 models are that highly detailed, they however are a hell of a lot more than WC3).
Next you would need to totally reainimate the model due to the physics supported in SC2 so that it functions properly (you could use the WC3 animations as a guide line for the SC2 animations but in the end you will have to create them yourself and probably add additional animations).
Then you will have to make the textures, this will be a hellish task. You firstly use the WC3 one as a guide to where all the parts are, separating out areas to paint. You then will have to split the image 2-3 times for all the different maps (and learn what the hell they do). Then is the hard and tedious part of painting all the parts. All these images will probably require you resizing it to 4096*4096 pixels for painting and then downsizing to 1024*1024 for final use so that you can easilly generate enough high frequency data for it to justify the resolution (unless you literally paint by pixels which I seriously doubt artists do).
Done? no... You then need to make separate death models...
Thus high resolution textures for WC3 models can not be justified. High resolution textures for WC3 models ported to SC2 can be justified, but will take so much work your better off starting from scratch.
Thus with all honestly, I advise sticking to normal WC3 texture resolution and detail for WC3.