Yes tea is a good option, I've done a bit of reading on L-Theanine and tried some caffeine pills paired with L-Theanine with fairly good results. Supposedly it negates the negative effects of caffeine and you don't build a tolerance to it, but I'm not entirely convinced.

I really like your water and exercise idea though, that would certainly be a nice substitute!