Funny you should post this. I just received my old M2 back from cameraleather today with a spiffy verdigris goatskin covering on it. It looks great!! I let them do it since they have all the experience with removal of old vulcanite from camera bodies. The extra cost was pretty reasonable.
I got a replacement leather kit for my M4 from Cameraleather and put it on myself per thier instructions. The hardest part was cleaning off the old vulcanite, but it was very doable. I should add that I am not usually very adept at this sort of thing, but would do it again, and, in fact am looking to recover a Rollei 2.8F with another one of thier kits.
Depending on your camera, it could be very easy or very hard. I sent Morgan (at cameraleather) my F2 so he could get the pattern down- he sent it back to me with new leather on. I eventually had to take it off and put it on another F2...anyway, its much easier than regluing your original leather- he uses little adhesive strips that are quite strong.
I only hear good things about them on other forums, mostly from people on a Leica forum. I purchased covering for my Minolta Autocord TLR and it fit perfectly and looks good. The only negative is you have to keep after Morgan for delivery. He gets busy and a little bit of the "squeaky wheel" theory applies. But from posts of dozens of people I've never heard a bad word.
The hardest part of the process is usually completely taking the old covering off not putting the new on.