I'm not sure what Mail app you're using. I use K-9 mail and have 4 email accounts feeding to it but I have restricted each one to only deliver 20 messages at a time from each one and poll every 30 minutes. That keeps the amount of mail on the phone at any one time to a minimum.
Also try free app History Eraser (it's like Disk Cleanup in Windows). You can choose what you want it to clean or just choose Clean All. It wipes old SMS, MMS, browser caches, browser search histories, etc.
Also get Astro File Manager which will let you find temp files and crap left behind by uninstalled apps that didn't clean up after themselves.
But it really sounds like you need to manage your mail first. I've got ~140 apps and very few, mostly large games, on SD card and still have over 1gb internal memory left.
You mentioned it wouldn't let you clear the cache. Try Force Stopping your Mail app first because if it is running it is probably holding the cache file open.