I want to add an include_path but don't have access to php.ini
settings.php would probably be the safest bet. 

The template.php file might well be included too late in the process to have the desired effect, but settings.php is included indirectly from drupal_bootstrap() so should take effect before any of your custom code has a chance to run.

If you don't want to alter settings.php in that way you could implement hook_boot() in a custom module which is also invoked very early on in the page build process.