[Cryptography] mode of operation for file encryption

[matic at nimp.co.uk]

I need an operation mode for AES with the following properties:
1. secure (ie. not ECB)
2. allow to do both encryption and decryption on blocks taken in a 
random order (ie. not CBC, CFB, OFB, PCBC)
3. not involving a nonce (ie. not CTR)
4. fast, especially when done in software running on PC / smartphone 
kind of platform:
  a. ideally a single AES per data block
  b. ideally always using the same key to save the key schedule effort 
(that is a saver at least on intel CPUs)

... kind of demanding!
On the bright side:
- a fix amount of data can be attached to the Cipher text if that can 
help.
- no specific requirement with regards to error propagation or 
authentication (well, for the time being)
- don't mind to have extra key material (without going to the extreme of 
things like one time pad...)

So far the best thing I can think of is a kind of extended ECB which I 
would call "ECB with xor" or ECBX:
C = Ek(P xor IV xor BlockIndex)
P = IV xor BlockIndex xor Dk(C)

where:
P is a block in the Plain text
C is a block in the Cipher text
IV is a 128 bit number attached to the Cipher text
BlockIndex is the index of P in the Plain text or C in the Cipher text, 
coded on 64 bits
Ek is AES128 encryption with the key "k"
Dk is AES128 decryption with the key "k"

The application is file encryption done on the fly in a virtual file 
system (the encrypted files are backed up in the cloud, the files are 
decrypted only locally on the end user machine). The bad guys have 
access to the Cipher texts only, they may be able to submit chosen plain 
text but in any case the IV is not under their control and would be 
chosen at random each time a file is created or overwritten completely.

Any alternative, reference to published stuff or criticism would be 
highly appreciated.
I could go for XEX, but I would like to have a good motivation to 
justify the additional GCM operation.


Sebastien