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)