Fundamentally, there is nothing that can solve this issue in the absolute. You're running into the DRM problem, which is that you need plaintext access to some data on a system in order to fulfill some functionality, but you're also placing that system under the control of a party which is untrusted. The best you can do is make it incredibly difficult for all but the most determined and skilled attackers, essentially making it a poor a cost/benefit trade-off for them.
In terms of solutions which do make it hard, devices such as Hardware Security Modules (HSMs) should be pretty much top of your list. They utilise a range of features designed to make it exceedingly difficult to recover information from them illegitimately. For example, a common feature is to encrypt data with a key stored in volatile memory (e.g. DRAM) on a separate board, physically attached to the upper casing of the device. The power and data connections for this board are supplied via a contact connector (often made from conductive polymer or foam) via pads on the main board, which is physically attached to the lower casing of the device. If you attempt to open the device, you separate the boards, thus disconnecting the power from the DRAM and losing the keys. Additional sensors such as light, temperature, pressure, acceleration and position (incl. GPS) and even magnetic fields or radiation can be present in order to detect different types of tampering.
One additional potential system which may, in some circumstances, be of use to you is the concept of homomorphic cryptosystems. Homomorphism, in laymen's terms, is essentially the property of a cryptosystem that allows certain operations to be performed on data in its encrypted form, without needing to first decrypt the data. There are a variety of schemes available, some of which are even practical for certain types of scenarios, but they are usually quite complex in nature and can be particularly slow. I am unaware of any existing cryptosystem which provides homomorphism in a way that would be conducive to cloud storage applications.