What is the name of a Cartoon Network anime whose second season plot was based on time travel?
It is indeed Xiaolin Showdown. 



It was broadcast between 2003 and 2006 consisting of 3 season. Each character was master of an element:


Big dude (Clay) - Earth
Girl (Kimiko) - Fire
Dot-Head (Omi) - Water
Remaining Boy (Raimundo) - Wind


It's actually an American production, but set in Asia. They protect the Shen Gong Wu from the evils that desire the treasure.

The first season ends with their failure and they need to travel back in time and create an alternate future resulting in their success. This is what the second season mostly deals with. In the third and final season the warriors travel to the Ying-Yang world to retrieve Omi's good chi.