Parallel authentication of encrypted data. What AE type to choose? I've got a system with a slow data transfer channel. Transferring a message through several channels does increase the transfer speed significatnly.
 AES-CBC+HMAC is good except that verifying the MAC cannot be done in parallel.  Encryption can be parallel by using CTR, but MAC calculation still needs to be sequential.

I looked at some AE modes like GCM, CCM, EAX, OCB, etc (actually I'm reading this document: http://www.fi.muni.cz/~xsvenda/docs/AE_comparison_ipics04.pdf ), but still cannot find one that meets all my needs. 
Here're the main requirements:


The decryption and verifying integrity must be parallelizable.
The encryption is not required to be parallelizable.
The Message can be of any size. Well, at least up to 100 TBytes. 
When encrypting data, the message size may be unknown. So "online  processing" is required for encryption. 
High performance is not required, because the data channel speed is the bottleneck.
No patents.


It seems that GCM mode is a way to go, except that it doesn't meet the requirement #3. According to NIST 800-38D GCM supports messages only up to 2^39-256 that is ~512 GB only. However the doc I referenced before states that GCM supports online message processing (without knowing the length of the whole message). Am I missing something? Because having length limitation seems to imply inability of online processing.
Use AES-OCB.  It is patented, but now has a free license for any non-military software use.  Unlike most other CAESAR candidates, OCB has been scrutinized for a while now, and meets all of your criteria other than 6 (assuming you have a good AES implementation).  

If the patent is simply too much for you, then use a heavily scrutinized patent-free tweakable block cipher like Threefish in a patent-free mode like Tweakable Authenticated Encryption (TAE) mode.

But, as CodesInChaos points out, you should also break up the message into several pieces and authenticate each piece independently, so you don't waste all day downloading 100 Terabytes that you have to throw away because a single MAC tag at the end doesn't match.  Remember, there are other ways to attack you than just message forgery or breach of privacy - maybe a hacker would be satisfied just wasting your time.