Help with new site design, using htaccess to avoid 404 pages

Hopefully someone can give me a few tips and tricks.  I have a large site, approx 4000 pages, which half static and half dynamic .  They have names like XXX.shtml because they use server side includes for data.  
My problem is, I have redesigned the site to use PHP and most of the pages are dynamic, I don't want to have people clicking on a google link and getting a 404 error because the old page won't exist anymore.  

I know that eventually google with switch to the new pages but what do I do in the meantime?
Should I use a redirect or a rename?  Is there some kind of global statement that I can use to avoid having to put in commands for 4000 pages?

Will a redirect work if the page being redirected from no longer exists?

I have played with .htaccess  a little bit but it seems to be black magic.

Thanks for the help
Ken Graser