Block Cipher Mode Amicable to Fast Key Change/Rotation Like XOR?
A better way to solve your problem is: on the server, encrypt the document under a document encryption key (a unique key that's specific to that document).  The document remains encrypted in storage encrypted under this document key.  When a client requests the document, send the client a copy of the encrypted document, as well as an encryption of the document key encrypted with the client's key.  Now the client can recover the document key and then decrypt the document.

This will be very efficient and will meet all of your requirements.  And, it is implementable using only standard cryptographic primitives approved in FIPS 140-2.

If you ever need to change the document, you should change its document encryption key to a new, unique key chosen independently of the previous version.  Re-encrypt the new version with its new unique key.  This way, users who have previously downloaded the old version of the document don't automatically get access to the new version (unless you decide they should be allowed to).  This lets you implement revocation to the extent that revocation is possible in this setting.  Thanks to DrLecter for this suggestion.