I know folks who hike in Tevas or Chacos.

I can't do it. Not because of the sole being inadequate - I cannot stand having to stop every few minutes to get twigs, rocks, bark, etc. out from under my socks, and cannot seem to walk ten feet without stubbing all my toes on something.

If I were you I would get a cheap pair of Tevas from Sierra Trading Post and walk around town for a while before committing to using sandals on a long distance trip. There are sandals with toe guards, true, but I find that stuff gets in anywhere it can, and stick to trail shoes.

Cold is going to be another issue. Those places you mention are going to be really cold in January. Get your socks wet and walk around in the cold and there's the potential for frostbite/hypothermia.