Drupal Caching and hook_init
A couple things here:


hook_init() will be run on the first hit on the page, eg, if it's not in cache already, it will be run and then the page will be cached.  But...
A page will not be cached if there are any drupal messages, so, when you call drupal_set_message() it sets drupal_page_is_cacheable(FALSE); and the page isn't cached.


ADDITION:

Regarding your additional code with respect to Javascript:  adding this code in verbatim here does not exhibit the random behavior you see on your site; eg; here the same number appears until the cache is refreshed.

Which made me think about this.  Check your cache times:



If the times are set to &lt;none&gt; I see the behavior you seem to experience, but when they are set to anything else, eg:



then I don't.