At the end of the day, you’ll be putting stuff into your .htaccess file. But, could speed things up via the following method…
You want to end up with two lists, taken from the wp_posts table. Both lists have the same fields/columns: Post ID; and Post URL.
List 1 – created without the posts being put into categories
List 2 – created after you’ve put them all into categories.
Then, as both lists will have the same Post ID column, you can merge them together:
`Old URL | New URL`
-------------|--------------
post1 old url| post 1 new url
Then you can generate a list of stuff to paste into your .htaccess file. You could write a simple script to turn each row in the above list into:
Redirect 301 post1/old/url post1/new/url
There are an infinte number of ways to go about doing each of the above steps, but I’m sure you’ll be able to figure one out. Will be basic PHP and MySQL queries. Maybe it will be possible to generate the first two list directly from phpmyadmin and export as CSV.