New link design - need help

Hey, a friend asked me to do some SEO for his shop. The first thing I noticed is the bad link design. It looks like this: http://www.domain.com/catalog/index.php?pid=123456 for each product. So I am going to change this to : http://www.domain.com/catalog/123456/name-of-product My problem is: What do I do with Google (around 60000 indexed)? I mean I cannot write a rewrite rule because I dont know the product names for each product. I can only do some rewrite rule that goes from http://www.domain.com/catalog/index.php?pid=123456 (old) to http://www.domain.com/catalog/123456 (new and works, but still not what I want). On the one hand I cannot rewrite all old URLs with the new ones (at least not with product name) and on the other hand I cannot allow dublicated content. Any suggestions for me? Thanks!