I love this one.  

Like you said, but an extension of what you suggest, have the check-bits being searched for as a function of the previous mined block.  Instead of searching for 00000000000 starting at nth 0, search for 76436753432 at nth 7.  Or that at 21, going backwards.  21/20/19/18/etc.  Or pick the Xth prime, and skip the Yth prime of each element, where the primes used is a function of the hash of the previous block.

Introduce them as a randomized instantiation.  ~10/1000 is this new 'format'.  Then, after 1000, it's ~20/1000.   Have a new difficulty setting for these new elements.  Who cares if you get a virtually instantaneous block reward for 10/1000.  No different than chance happening for that normally.  By the time that it got to 100/1000 there would be an entirely new set of miners, on an entirely new set of difficulty settings.

It doesn't punish the miners that are currently mining in an untoward manner.  It gives them an acceptable return on their existing hardware.  That would account for a two year rollover.

Then, let the miners know that the same thing is going to happen again in two years.

It de-incentivizes hardware solutions, but doesn't kill them.  I'm not sure this solve the long-term problem of centralization though.  While the prime thing is good, you want all of that calculation to be done by the miner, with the least amount effort you can come up with so that it can be validated.  This just means that you could have relatively minor modification to the hash validation that current hardware wouldn't be designed for.  I don't actually know how the ASIC's verify that a specific hash meets the requirements of validation.  It might be as simple as updating a single variable within their hardware or software implementation.  Instead of looking for "000000" look for "123456".