A block cipher whose key changes after each block I have been reading about various block cipher modes of operation, and all of them seem to treat the block cipher (including it's key and key schedule) as a sort of immutable black box.

I would like to know whether or not any one has designed a mode of operation where the effective key schedule of the cipher is changed between each block encrypted.

Suppose, purely for example, that we had a 256 bit block cipher, using a simple a 4 round Feistel structure.  The expanded key, generated from a secure hash of the user-supplied key and an IV, would be 512 bits.  In between each pair of blocks encrypted, we treat these 512 bits as the state of a 512-bit linear feedback shift register, advance the LFSR one step, then use the result as the scheduled key for the next block of data encrypted.

Like CTR mode, encryption and decryption are parallelizable, and it has the property of random read access.

Does anything remotely like that exist?

If not, is it because it would be obviously horribly secure in a way I'm not seeing, or for some other reason?
In general you want to treat primitives like block ciphers as black boxes. You first analyze and try to break the block cipher. Once it is proven to operate correctly you can use it as primitive for a block cipher mode of operation. The mode of operation can then be proven to be secure assuming that the block cipher primitive operates well.

If you don't treat the block cipher as a black box then you will basically have to show that the mode of operation doesn't invalidate the security analysis of the block cipher.



The subkey derivation may not be the most important part of a cipher, but that doesn't mean that there aren't many things to consider.



It seems that tweakable block ciphers do indeed provide an answer to what you want to achieve (see the answer of pg1989 and the comment of SEJPM).

Lets quote the paper that introduced them:


  Block ciphers (pseudorandom permutations) are inherently deterministic: every encryption of a given message with a given key will be the same. Many modes
  of operation and other applications using block ciphers have nonetheless a requirement for “essentially different” instances of the block cipher in order to
  prevent attacks that operate by, say, permuting blocks of the input. Attempts to
  resolve the conflict between keeping the same key for efficiency and yet achieving
  variability often results in a design that uses a fixed key, but which attempts
  to achieve variability by manipulating the input before encryption, the output
  after encryption, or both. Such designs seem inelegant—they are attempting to
  solve a problem with a primitive (a basic block cipher) that is not well suited
  for the problem at hand. Better to rethink what primitives are really wanted for
  such a problem.


That's from the introduction of the paper Moses Liskov, Ronald L. Rivest, and David Wagner: Tweakable Block Ciphers.