If not hook_init(), what can be used for cached pages?
I think you are asking the wrong question.

If a page is cached, it means that it got generated and cached at some point. At this point, your code in module_init() did run. If your code generated a redirect (via drupal_goto()), this redirect will get cached.

There should not be anything wrong with this scenario, so maybe you should just clear the cache once?