Is it necessary to use cache in hook_init? I wonder, since hook_init doesn't run on cached pages, is it useful to use cache_set in a hook_init() ? 

I am going to retrieve an array of strings from the database on each page request (not on cached pages obviously), so I am wondering how to do it properly. For this purpose, should I use cache_set, a persistent variable or maybe no cache at all in hook_init ?
Sure, why not. All three options should work fine. But using Drupal's cache mechanism will work the best. The page cache is not the same as other caches which can still be used for whichever purpose you require, in this case, to store the results of a DB call. There are a number of core caches each with their own purpose besides the generic one (simply named cache), and you can also roll your own cache table if you like.

Here's an example on using cache_set and cache_get which should be similar to what you are attempting to do (albeit not in hook_init).