It is probably possible, like mustyoshi said.
However, if that is to be done the difficulty has to be taken into account, since different hashing algorithms have different speeds. Moving from, say, SHA-256 to Keccak, would entail a significant hashrate alteration (some searching around gives me 12.5 cycles/byte for Keccak and 14.3 cycles/byte for SHA-256, a difference of ~15%), resulting in probable difficulty plunges or spikes. A good difficulty adjustment algorithm would be able to handle this properly.
If the re-target algorithm is fast enough, then this should not be too much of a problem.
I wonder what the effect will be for existing blocks that used the older proof of work.