richinberlin, you've chosen a tricky area, and you're sort of partway there. You've identified the basic issues and you're beginning to ask the right questions, which is much better than most. Yes, IMO, you need to avoid multiple urls for those otherwise identical product pages, so they won't be seen as dupe content. It's an area which can take hours or weeks to discuss, and on which, I should emphasize, there is still not a consensus.
My approach has been derived and guided by the work of a past member of these forums, username "g1smd", who was a pioneer in identifying and avoiding problems with duplicate content (including, I should add, canonicalization). In some of my comments below, I'm either quoting or heavily paraphrasing him.
-- First, it's not clear whether you're asking about...
a) setting up a new site...
-- or
b) making breadcrumb adjustments on an existing site
As you'll come to see, your simple choices are very limited on an existing site. To get this started, I'll give a further overview of the basic problem, describe the existing site solution firstm. and for new site development, give suggestions for further reading.
Basically, to make your situation as described in this thread's title workable... ie, products in multiple categories... the key is to have a unique url for each product page, make your product pages root relative, and keep each product page url separated from the category hierarchy path the user takes to get to that page.
Details will become clearer as you read the threads I reference (and perhaps read through this thread more than once)....
Stated another way, do not carry your directory and subdirectory names in the product page urls. Keep them separate. Important to note that nav structure and site structure are not necessarily the same.
You should hierarchically structure your html site... with categories and subcategories reflected in that structure... and keep the navigation paths out of the urls of your product pages. Again, make your product pages root relative... either from your site's root directory, or from a directory called something like /pages/ or /products/. I wouldn't divide them finer.
Breadcrumbs can be treated several ways, and Google should be able to pick them up from the approach you choose. Suggestions and details in the threads I'll reference below, which, as my time permits for now, have too many considerations to try to reproduce here.
Before I post those references, let me now go through the situations you outline in you opening post, and you'll have a better perspective yet on your choices....
1. Product in multiple categories. Multiple Urls. Multiple breadcrumbs. Canonical to main category + product url
I would avoid multiple product page url situations that depend on how Google (or any other search engine) sorts out rel canonical tags. Why give Google pretzels to sort out? Also, I'm not sure that rel canonical links are appropriate in this situation. This, IMO, should be avoided whether site is existing or will be built (or rebuilt) fresh.
2. Product in multiple categories. Single Url. Multiple breadcrumbs pointing back to each of the categories.
If you want multiple breadcrumbs, this is best for using an existing site with no major changes. In ecommerce sites, I like breadcrumbs for helping users navigate. You certainly can display several different breadcrumb paths on a single page, though multiple breadcrumbs may conflict and interfere with breadcrumb display in Google serps. I don't have current observations on that.
3. Product in multiple categories. Single Url. Single Breadcrumb
This of course the simplest for current site, perhaps most appropriate if you have a strong preference for the product page context... say, one which might lead to the most conversions.
Note that instead of additional breadcrumb links, you might want to use "find more" links, linking say to corresponding categories for the parallel navigation paths. (Could also be applied to option 2).
I'll link to the threads I have in mind in a second post, so this doesn't become too unwieldy.
