There's always some reason for scheduled downtime, but it can be minimized.
Depending on your infrastructure, different strategies can minimize downtime. Regular-old-updates ought not require downtime.
On a number of PHP-driven sites I manage, I maintain side-by-side copies of the codebase, let's say version 1.0, 1.1 and 1.2:
/sites/site-1-0-0
/sites/site-1-1-0
/sites/site-1-2-0
And then create symlinks that the web server can use:
/sites/production --> /sites/site-1-1-0
/sites/staging --> /sites/site-1-2-0
This way, I can stage my code on the production server for last-minute sanity checks, and when I want to go live, I just:
$ rm /sites/production; ln -s /sites/site-1-2-0 /sites/production
The web server uses the symlinks in the DocumentRoot specification, so the cutover is practically instantaneous.
There are, of course, gotchas, here. One needs to ensure that external data is stored somewhere, er, external. You don't want to be writing temp files, or storing user-generated content in the filesystem under the site-x-y-z directories.
Another alternative, if you've got multiple servers is to make the cutover via routing. Some VPS vendors (Linode comes to mind) make it easy to take two virtual machines and swap their IP addresses. So you set up your new version on a new server, do whatever testing is necessary, and then swap IPs to deploy your update. The same issues about keeping non-code assets up-to-date apply, but some careful thinking and planning can make that a non-issue.
With more robust, load-balanced setups, strategies like those suggested in danlefree's answer work as well.