Per unit of heat generated, natural gas produces about half the CO2 of coal.

http://www.eia.gov/tools/faqs/faq.cfm?id=73&t=11

That is already a big win.