4. An attacker should not be able to disguise his theft as a set of withdrawals initiated by customers: withdrawals should be signed with a private key derived from the customer's password; during the daily manual check, compare [a hash of] the set of password-derived public keys in the server's database to [a hash of] the password-derived public keys in your database backup.
Along a similar(ish) line, I implemented (for fun) a private-key sharing mechanism around the Armory python library... effectively you Shamir-split the private key of a user's deposit address, then only ever store one half on the server. The other-half must be given to the user and never persisted by the exchange.
This would potentially make quite a nice protection mechanism for long-term deposits or even initial margin balances. If the database was completely publicly exposed, you could just find the exchange's share of your key and retrieve your funds yourself. Might be a nice stop gap until multisig comes along.
Another possibility is to require users to make their first deposits from an address they control. Any password change, contact details change, etc. would then require the user to sign a server-generated message from that address (again Armory does this nicely).