The mainnet gas limit is 6.7M at the moment, which is actually higher than what your contract uses to deploy, so even in its current state it would be deployable there. When testing on http://dapps.oraclize.it/browser-solidity/ which is Oraclize's browser-solidity/Remix fork, with an included Oraclize bridge module, you can actually test your contract right on the JVM, no need for a testnet, in which you can change the block gas limit to whatever you desire.
However, a better solution is of course to go with a modular design of your contract, where different parts, such as the storage and logic, are in separate contracts, which connect to each other via a central resolver. This modularity also helps with integrating some potential update features. In addition to separating the above, you can leverage Oraclize's api library as well, which will end up being deployed separately from your main contract, but will be linked and do delegate calls to the library: https://github.com/oraclize/ethereum-api/tree/master/lib-experimental
Note, it is considered experimental, but we are using it in some showcase demos of ours, successfully and without issues so far.