So. I had this crazy idea, when I was reading the book - what if the traveller is Sarl? We don't really know that the traveller left the company, because the scene ends with "We want you". Sarl talks instead of the captain, so he could be making decisions in his place. And he is almost always with the Captain, yet when the traveller first meets Lord Kosoter, he is accompanied only by Cleric sitting behind him. And then there's this scene in Marrow, where Achamian observes Sarl "pretending that he is one of them [Skin Eaters]".
Although now, having read all your posts, I don't think it's the best idea.