I'm assuming all items are currently setup with the same tax status.

It depends on the answer to these two questions - approximately how many items are taxable for a taxable customer? How many are not taxable? If the answer to either question is under 50, then it is easier to edit each item than it is to do an export/import. You would leave the majority alone, and change the remaining items to a new tax status.