Show Cart Module everywhere EXCEPT during checkout

Yes. You need to set the option "force a menu on the checkout" in the config under the tab checkout and then change the cart module's options so that it doesn't display on that page.

Well, that's indeed how it's done. The itemid doesn't change when you click on a product link of the cart.
If you want to set another itemid in the links, you should edit the file cart of the view product via the menu Display->Views and change the line:
$url_itemid='&Itemid='.$Itemid;

to:
$url_itemid='&Itemid=XX';

where XX is the id of your menu.

You need to choose there a menu where your module is not assigned. If you don't have any, then yes, create one and make sure that your module is not assigned to it.