My first thoughts, when meeting him in HoC, were that he was just a person. When I read NoK, I didn't even think about him, but having just read the start of the fourth chapter of TtH, I'm convinced it's Dassem Ultor.
NoK has a few flashbacks which concern the breaking of the Sword of the Empire at Y'ghatan. Dassem survived, along with two others of the Sword (a group of five 'bodyguards' and Dassem), one of whom is a key character in the book. The two and Dassem parted ways, with Dassem saying he needed to travel alone, to find something.
Traveller is of average height but seems a lot taller, dark-skinned, and had sword skillz that truly pay his bills. Dassem Ultor was of avergae height, dark-skinned, and was the First Sword of the Empire - a position that obviously meant he had amazing sword skills.
And that's all I have to go by, actually... seems so little, now I look at it.
But yes, I'd put my computer on Traveller being Dassem Ultor. Don't forget that Keeper, who lives in a tower and re-builds skeletons turned out to be Urko (wasn't he?).
EDIT: I mustn't forget to add the clincher - Dassem had foresaken Hood, which if not mentioned in an Erikson book was mentioned in NoK. At the end of the passage in TtH in which we first see Traveller, Erikson casually remarks that Traveller had forsaken Hood, so the final gate was closed to him. Coincidence, or same person?