Actually currently we have few active accounts with deposits as we just started. At the moment all coins are in "hot storage", but the amount is lower than the capital reserves of the company. So at this moment the hot wallet is 100% insured, as if storage would get hacked, we will pay out of own pocket the losses, which at this moment is only 30BTC, and in cold storage (own capital) we have around 200btc (company capital). It is company policy to have 90% in cold storage as soon as we have more deposits, such that it makes sense to place it in cold storage. We could also put 100% in cold storage, but its important for people to be able to immediately (not all at once) withdraw, because traders might need to send their capital to another exchange urgently, or for which ever other reason. (if hot wallet goes empty, trader would have to wait untill we replenish the hot wallet, which we check once a day).
As for "verify" cold storage address... the address being cold or not is impossible to verify. We understand that the big issue, specially for us being a new exchange, is the trust people have in the platform, and we surely need to do something about that to gain trust.
so...at this moment its actually 100% hot storage, but 100% insured with cold storage...which is even better. If hot wallet gets hacked...we will refund 100% all accounts. And it will stay this way. Our hot wallet will never grow bigger than our cold wallet company capital, such that we always can guarantee client funds even in the case of a hack.
Sure it is impossible to prove that an address is in fact "cold" and "cold storage" differs from person to person, however you could sign a message from an address (or collection of addresses) that are holding your cold storage BTC. The concern is not so much that BTC is being held "cold" but is more that you actually are in possession of the BTC that you claim to be in possession of. This would especially help considering that you are very new.
Another thing you can do is publish proof of liabilities by publishing a hash of some ifebtifier of user accounts and the corresponding balances in their accounts. This would help prove that you are not running on fractional reserves.