Yes, credit memo and new invoice.

With a bit of form work, you could also just credit the tax.  Two misc charge lines (against the same GL account), one plus and one minus, one being taxable and the other not.  Suppress the lines when printing the form, and you'd just see the - tax amount at the bottom.

It depends on what you want to have to send to the customer.

I agree with Kevin.  Do a credit memo with the two line that do the positive and negative so the only change is just the tax.  Doing it that way will make sure your sales tax reports are accurate.