All the emails that were filed under labels in gmail have been totally deleted. Can they be retrieved?
I have deleted: sent mail, trash, spam etc and I still get the message that my cache is full. What do I need to do?

Assuming you are referring to webmail and NOT via a client such as outlook, I'm sorry to say they are GONE for good.
That's it game over.