I was thinking of permuting bits in a block before it is hashed, in order to require some adaptability from the mining hardware while retaining the security of SHA-256.
Permutations would depend on the hash of the previous block so that they cannot be anticipated. They would also depend on the nonce, so that the permutation step would have to be performed once per hash, preventing a single external CPU from efficiently preprocessing the data.
A simple example of algorithm:
Seed a pseudo-random number generator with the hash of the previous block appended to the nonce. Draw 1000 pairs of pseudo-random numbers between 1 and the length of the block in bits. Swap the bits corresponding to these pairs. Hash with SHA-256.
It seems to me these permutations would be particularly troublesome to implement electronically, and I was thinking this might drive up the cost of ASIC implementations.