I stumbled upon a way to remove an attachment and keep the message. It's a few steps, but it works.
Before you try this, you must enable IMAP in your account settings.

Next, set up your accounts. I use Mozilla Thunderbird, but you can set up IMAP accounts in Outlook and just about any other e-mail program. I’ll skip the instructions for that, but they’re all pretty much the same. When you create the account, just make sure you set it up as IMAP instead of POP.
When you get a message with an attachment, either open it or have it showing in the preview pane.

Right click near the attachment and select “Delete” (or “Delete All...” for multiple attachments).

Confirm that you want to delete the attachment. You’ll notice that the message disappears from your Inbox. Not to worry. Expand your Gmail folders and go to “All Mail”. Now you’ll see two messages. One without the attachment, and a duplicate with the original attachment. You’ll also notice that the message you removed the attachment from has an attachment icon. For some reason Gmail adds a note the stripped message letting you know the attachment was deleted.

The last step is to drag the attachment-laden message into the “Trash” folder, and you’re done. Now, you’ll get more out of your Gmail storage.
For those of you inclined to send large files, please use the various free services that allow you to send links to files up to 100mb. You’d be doing all of us a favor.