Changing entire internal link structure and Google

What is the best way to do this?

[Ivan_Bajlo]

No I'm not crazy just something I got to do so I better do it sooner then later...

My wargaming/history multilanguage website has some 1500 visitors a day and over 2000 individual pages/files in asp (don't ask), bunch of include files are one keeping entire mess together. ;-)

My directory structure is massive I've made several hundred folders just so I can keep track of everything on my site! ;-)

It looks something like this:
widgets.net/default-es.asp
widgets.net/default-de.asp
widgets.net/default-hr.asp
widgets.net/bluewidgets/default-fr.asp
widgets.net/redwidgets/.../small-ru.asp
... etc.

You get the picture.

So now I finally got to the point were keeping site update is impossible and I'm planning to move it to MySQL database and get nice CMS to power everything.

Since old directory structure makes a little sense I'm planning to replace it with something that will make lot more sense (generated from database of course):
widgets.net/eng/british-widgets/small/red
widgets.net/fra/français-widgets/petite/rouge
widgets.net/rus/
widgets.net/hrv/
...

Many of my pages literally haven't been touched since 1999 even after I moved to current domain in 2003 - they are literally white pages with black text ;-))), also there is lot of bad English in my early texts that needs to be fixed but that will happen slowly.

My problem is best way of solving old pages redirect with minimum damage from Google - horror stories on this forum aren't very comforting.

Most outside links aren't that much of problem since most of them link to my main page, several links from Wikipedia to my historical articles are easily changed and being DMOZ editor and Zealot will allow me to fix some of my links there. ;-)

Since huge number of links needs to be redirected it will probably be job of some PHP script to sort them out and redirect them to new address, but reading this forum made me unsure if 301 is right way to do it or should I have 404 page created and link to new page for humans and no follow tag for robots or is there better solution?

Also how would Google react to completely new sitemap? Dump all the old links and go my site banned?

I got burned during Bourbon when my ancient site took over new one but after killing it once again (darn zombie) and few e-mails to Google got back to normal.

And for last should I wait until January or risk it in November? ;-)