I think you’ll need to have your email marketing software handle this, they might have the feature.
For example, with an app you can add / remove customer tags when certain events happen. In your case the event happens with your email software, so when they get that event, they can make the API call to your customer to remove the tag.
I would contact your email software provider and ask them “do you have the ability to remove a customer tag in Shopify if there is a customer with the email address that unsubscribed from the newsletter?”
It’s probably unlikely because they would have to search all your Shopify customers to see if the email address matches, but might be worth a try.