Preventing "padding oracle" attack if data is streamed or too large for HMAC?

I know that the best solution against the padding oracle attack is to wrap and append a HMAC to the complete encrypted message. But what other solutions are there? What if my data is so large that I need to stream it? I can check the HMAC at the very end, but I cannot afford loading the whole file twice and check the HMAC first and then stream and decrypt it to the user?

Are there different ways?

Can an attacker also do padding oracle attacks if I use AES_CBC(zlib(data))? zlib will emit errors if the compressed data is garbled eventually. Can an attacker use that error of zlib to get one bit of information, too?

The suggested fix for the padding oracle attacks is to Encrypt-Then-MAC. This means that you can break the ciphertext up into conveniently-sized blocks (say, 4096 bytes) and MAC each individually.