The leather you are looking for is called sole bend. Cut the pieces a little too big, contact cement them together. Grind them to fit with a belt sander. Before you install the heal, clean up the front, install the deal and then shape the sides and back. You will also need a piece of rubber sole to use as the bottom of the heal, unless you are fond of slipping and falling down. The heal is nailed on, I am not sure how it is normally done, short nails through a couple layers or longer nails.
As to reshaping the heals, maybe someone else will speak up but it is my understanding that your gate will be off if the heal drops straight down.
I am far from a pro, but I have been trying to learn shoe stuff too.