Is it possible to redirect users when page caching is enabled?
Usually no. Not like that.

Caching systems are created to serve content with as minimal as possible PHP execution. If you use varnish, nginx or similar cache, or Boost module, you ay even not have any PHP executed at all. And even if some parts of PHP are executed, theming layer is usually omitted, because logic shouldn't be there - and if logic shouldn't be there, then that's exactly the part that is (or should be) safe to cache.

So first, try to move logic from template to some module, and second - learn about the caching system you are using, and how to add exceptions to it (if just moving the logic does not fix it for you already).