Avoiding PHP timeout when geocoding many addresses - preferred method?
It seems to me that your only option is to go with a PHP CLI script implementation. You can learn more here: http://www.php-cli.com/

In PHP in general, whenever you have a long running task, it's best to go with PHP CLI as it doesn't impose a timeout limit and have larger memory limits by default. Note here that PHP CLI and the PHP used to server web pages have different settings that you can manage separately.

Once you have a PHP CLI script in place, setup a standard Linux CRON task to hit that script say every hour or every day.

In the context of Drupal, you might want to check this post: Do I need a cron task for processing a queue? and also check the Elysia CRON module https://www.drupal.org/project/elysia_cron as they might be helpful but I think in your case you're better of with a standard PHP CLI script.

Also, keep in mind that you can call Drush commands from a PHP CLI script very easily. I have a script that runs updates and CRON automatically on all Drupal instances running on web server and it's a huge advantage. You can also look into implementing your custom Drush commands.

Good luck.