Many mailers use the mailto trick where one needs to send an email with "Unsubscribe" in the subject to unsubscribe.
Create a mailto link in your newsletter. Perhaps add a body with some text telling the user that sending this email will unsubscribe them from the newsletter.
<a href="mailto:[email protected]?subject=unsubscribe">Unsubscribe</a>
When the user clicks the link, their mail client should pop up a new email with the To and Subject pre-filled and ready to send the "unsubscribe" email.
When you receive the email on your server, extract the From field to find who to unsubscribe and if the Subject is "unsubscribe", then unsubscribe them. Of course now you need to deal email forging, if that is something worth tackling.