Did you check with your hosting provide regarding increasing the max_execution_time? If PHP is running in safe mode, your modification to the max_execution_time may be ignored. This will depend on the hosting provider’s configuration, and they should be able to assist.
If you have shell access to the machine, this can all easily be worked around by running the upgrade via command line instead of via the web interface. There is no max_execution_time from the command line (CLI).