Without doing database replication between the two sites, the best you can do is:
a) check your logs for your low periods of activity and set this as your maintenance period window.
b) send out/post on your site an advanced warning that you're making some changes (and I'd mention that the new server is faster, etc. so there's a positive effect for the downtime).
c) set your DNS TTL to 1 hour for several days to a week (depending on what your TTL was before you change it) or so ahead of your maintenance window; a week is safe.
d) change your old site's home page to "We've moved, etc." and having created a new.yourdomain.com A record that points to the new server, put a link to it on the "we've moved" page for those users who happen to hit the site during your maintenance period and/or if they're DNS was/is cached; make sure your site's database/code (cookies and session etc. can cope with multiple domains, it should though).
e) change your DNS A records to the new site; over the next few days change your TTL back to something more reasonable (3-6 hours is fine, although some say 24 hours is "standard").
You could also look at transparently redirecting requests (port forwarding, etc.) received by the old server to the new server, but I'm not sure how much control you have over your old hosted environment.