Is there a way for Avatax to not include Shipping Charges in the Total on an Invoice? I've never setup Avatax and their help doesn't mention it directly. Maybe map shipping item to a non-taxable tax code?

I think you got the right idea. Shipping Item that has a taxschedule which is not the avalara tax schedule

Yeah this just smells like its a setup issue as Avatax should know which states do and do not charge for certain things like shipping.

look at the Avatax freight codes. some states has shipping taxable, some are non taxable, depending on if you give your customers the option to arrange freight. Some tax all the time no matter what.