I believe we are talking about the insole and not the 'sock', the insole liner (which AE doesn't use). You cannot replace the insole without a major remake of the shoe.
If the stuff is sticky (glue), you might have to use some alcohol to remove it. Then you take some fine steel wire wool (DIY shop), take a small ball and go inside the shoe and rub with the wire wool over the insoles. That will remove all the markings from the insole. leaving just dust inside the shoe. Remove the dust with a slightly damp cloth.
That leaves you with a squeaky-clean insole. Works wonders on insole with dark sweat stains.
