The best workaround this would be to download/delete your emails. Downloading them for backup and storage sounds to be the best option. A great way to do this is by using a desktop app, most notably the best would be Mail on Mac OS X and Outlook or Thunderbird on Windows.
You should go ahead and do this by date (in my opinion), you won't be needing older emails more over newer ones on gmail.
Go ahead and load up the client of your choice, and you can export emails using export/archive functionalities.
Here's e instructions to the specific app:
I would suggest using a different name on the file just to make it relevant and backed up. It might take awhile to download all your messages in apps like Thunderbird where most email accounts (esp Gmail) are IMAP.
After doing this, you will probably have all or most of your space back. Also, if you think this is too laborious, you should just go ahead and buy more storage from Google, 5 bucks a year for 20gigs.