A list of most locations can be found here as there's a lot to list: Tibia Wiki - Scavenger Hunt
According to Skerio on the forums, the Time Traveller Tourist appears for 40 minutes and disappears for 20 minutes. -Source
Thais Ancient Temple
Okolnir - Frost Dragons
near the entrance to Drefia
Oramond Bridge on way to Minotaurs
Serpentine Tower
Deeplings in Gray Beach
Wasp Tower in Darashia
an Island in Feyrist
Venore Swamp near Amazons
Meriana
Found him on the way to Draconia in Hellgate!
Ab'Dendriel Tree
Ab'Dendriel - Opticording Quest
Ankrahmun in Green Djinn entrance
Venore Shipyard (The boat near bugs, not the main Venore Ship Boat)
Kazoordoon near Emperor's Room/Cookie Quest
Nargor on the Ship
Darashia Catacombs (Blue Legs Quest)