Could an algorithm be made ASIC-resistant by simply adding deterministic permutations depending on the hash of the previous block and the nonce? 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.
Your solution will least at most a year until dynamically reconfigurable FPGAs appears in the market. Then creating any logic circuit on the fly will be possible, and so efficient FPGAs will outperform CPUs by a large margin.

See for example: http://en.wikipedia.org/wiki/Partial_re-configuration