How to remove dates from existing permalinks?

You’ll find this post by Joost De Valk on changing WordPress permalinks to only include /%postname% very helpful.

How many posts you have doesn’t matter anymore if you are using the latest version of WordPress (at least > v3.3.1).

I believe your permalink structure initially was — this /blog/%year%/%monthnum%/%day%/%postname%/ — and now, you are planning to use a much simpler one — /%postname%/ — amirite?

If the above is true, you just have to add this rule to your .htaccess file, and it should take care of all the 301 redirects for you:

RedirectMatch 301 ^/blog/([0-9]{4})/([0-9]{2})/([0-9]{2})/([^/]+)/$ http://www.thedomain.com/$4

And since it’s a 301 redirect, yes, Google will eventually know that the post has been moved to a new URL.

EDIT: By the way, the redirect rule doesn’t require mod_rewrite. It uses mod_alias which is enabled by default by most (if not almost all) hosts.