I've done that myself, and had it done by ordinary shoe repair places. Success depends on the material of the shoe, the care you (or the cobbler) take, and just how perfect you need the outcome to be. The edges of the pump or sandal are the iffy part. BTW, suede CAN be dyed, but it's tough to keep it from becoming shiny.
ETA: Isn't there already a thread on this?