[andor436]

Heat pump! You can get wall mounted units that work just like an A/C (but in reverse of course.) Efficiencies have gotten pretty good in the last decade. Check out units made by Daiken, Hitachi, Mitsubishi for example. I know they make multi-room versions. You'll need to run the refrigerant lines, but that's usually a much smaller task than adding ducting.

[aidenn0]

This is the direction I'm most likely to go. The other option is a fireplace insert. Cheap, but not as environmentally friendly.