Modifying my theme's template.php requires apache restart to see changes
Thanks to Clive and MPD, that pointed to the answer.

It was because of APC. 

I've installed the module apc_admin, which allows to access the APC interface (apc.php) from within drupal (Configuration » Development » Performance » APC).  That includes the "Reset APC cache" button. Just by pressing it, the changes in my template will show up.

Hope this helps also other users.