Crazy idea: gas powered heat pump. Instead of just burning gas right into a heat exchanger as a furnace does, it burns it in an engine which turns the heat pump compressor. The house receives all of the heat transferred by the pump as well as the exhaust heat.

It's essentially the same thing that would be happening if you had a grid burning natural gas for electricity powering an electric heat pump, only it all happens locally and the exhaust heat is utilized. It's also similar to a "micro combined heat and power" system, with the power going directly into a heat pump.

EDIT: just discovered there's a smarter/simpler way to make a gas-powered heat pump: https://www.energy.gov/energysaver/absorption-heat-pumps.