I thought I had the problem licked by using Discounts (instead of Free Shipping flag on each product), via adding the Discount requirements "Customer has one of these products in the cart" and ANDing it with the "Shipping country is" Requirement (I created another Country called "United States - Alaska & Hawaii" to partition out those 2 states that won't have free shipping and removed Alaska& Hawaii from original "United State" country), then choosing all the products in the category. It would seem to work, however, it applied the 100% Shipping discount to the entire order instead of just applying the 100% Shipping discount for those specific products.
What I need is another Discount Type altogether, such as "Assigned To Product Shipping" that only affects the shipping costs on a product by product basis, with the ability to add the other requirements as found.
Currently, we have:
Assigned to order total
Assigned to products
Assigned to categories
Assigned to manufacturers
Assigned to shipping <-- only for shipping total, not individual products
Assigned to order subtotal