Using Magento's canonical feature will be the easiest way to resolve this problem. The only downfall is it won't include the category names and may miss out on additional keywords in the URL. Developing or purchasing a module is the next best way if you have the programming skills or budget to do so. If you're on a limited budget, you may get able to get away without spending any money if you're comfortable doing some modifications and data entry/database import.
I'm not a very good programmer but I got around this adding a new attribute, say canonical_category. Before Magento 1.8, I was able to override the $categoryid with a new value based on the category IDs. For instance, whatever I wanted to set as the canonical link, I would just enter a number in the new attribute field and it would generate a link with that category.
Magento 1.8 is slightly different, as they looked like they updated that section. Unfortunately I can't look at it now and tell you how to get the same functionality, but I quickly went through the new code and put together a workaround in case it may help you.
The file that needs to be modified is /app/code/core/Mage/Catalog/Model/Product/Url.php. On line 267 we'll find the code that handles the canonical link, function _getProductUrl. Basically we're going to use the canonical_category value if available and just fallback on the original code if nothing is entered.
So we'll change this line of code:
if (!empty($requestPath)) {
return $this->getUrlInstance()->getDirectUrl($requestPath, $routeParams);
}
to
if (!empty($requestPath)) {
if($product->getCanonicalCategory()) {
return $this->getUrlInstance()->getDirectUrl($product->getCanonicalCategory());
} else {
return $this->getUrlInstance()->getDirectUrl($requestPath, $routeParams);
}
}
Just to be clear, all this will do is let you specify what you want your canonical link to be, in your case you want to include the category name. Your links to the product page will still appear to be the same (square-grate.html, /cast-iron/square-grate.html) but from what I understand the search engines will still treat this as the same page as long as a canonical link is specified. This should resolve the SEO issue but now there is more work if you want a specific link to be used. I can tell you any method that is not done dynamically is not the best way, but it will work and you can update/generate links easily via spreadsheet and database import. You can also just use it on products that need to include the additional [category] keywords. Note that the URL that is entered for the attribute should be relative (ie "cast-iron/square-grate.html"). Hopefully this helps.