How do I cook lamb tongues?
I would try simmering or braising until they are tender, which will make it easier to then skin them.  Stewing them slowly, like you mentioned works well especially if you're making a soup.