There are many solutions to this. https://blog.ethereum.org/2014/06/19/mining/ Some involve doing nothing as market forces and economics will force decentralized miners to be used for heating.
Economics are already pushing miners to go green to compete with sunk electrical costs -
In the future it is likely that all electrical costs will be used create the product of heat with PoW as a nice consequence that helps subsidize the energy bill or ASIC appliance.
What this means is the PoW could go from being much more environmentally friendly than fiat to much greener.