You could set up a second mailbox specifically for unsubscription requests, then add a link in the email body like you mentioned but just make the link a simple mailto: that points to the unsubscribe mailbox.
You would still have to remove the addresses from the list manually, but you wouldn’t have to search through any emails to find the unsubscription requests. It would also be a little less clunky for the unsubscriber: although they still need to send the email, they wouldn’t have to edit the subject line or anything first. Just click the link and hit send.