If you really need to change your permalinks, use Dean's Permalink Migration plugin. It will make sure they are redirected for you.
Letting links 404 is really bad. I'd take the time to go in and redirect them.
Anyone can do a redirect. Just go into your .htaccess file, and add something like this for each post that is getting a 404 error.
There are many ways to do it, you can make rewrite rules using regex to handle alot of them, but this will do the job
Redirect 301 /old-url/ http://yourdomain.com/new-url/