This question can be answered using a Life Cycle Analysis, which looks at emissions over the total life cycle of a product - including manufacture, use, and disposal. Many such studies have been performed, here are two examples:
A 2012 UCLA study for the California Air Resources Board, and
A 2015 study by The Union of Concerned Scientists
Both of these conclude that electric vehicles produce lower greenhouse gas emissions than conventional vehicles using California or US electric mix.
From the UCLA study (where BEV means Battery Electric Vehicle, and CV means Conventional Vehicle):
In terms of environmental impacts, the BEV was determined to have the least overall impact, followed by the hybrid, and lastly the CV.
Here is a chart from that report showing the life cycle impacts using California's electric grid fuel mix [coal (7%), nuclear (14%), natural gas (42%), total hydropower (13%), wind (5%), geothermal (5%), solar (0%), and biomass (2%)]. The Battery electric vehicle emits about half the CO2 of the conventional vehicle over its lifetime.

The question specifically asks about the worst case for CO2 emissions - a country where most electricity comes from coal. This is also addressed in the CARB report, through the following figure which looks at different electricity mixes. The study used this mix for China: coal (79%), nuclear (2%), natural gas (2%), hydropower (16%), oil (2%), wind (0%), geothermal (0%), solar (6%), and biomass (0%).
The BEV emissions from the China electric mix are about 2.25 times higher than for the California mix, which would put them at slightly higher than a conventional vehicle, based on the first figure.

It is clear that the cradle-to-grave CO2 emissions are comparable to a conventional vehicle in the most coal-intensive electric grid, and considerably better as the percentage of coal drops. Given that the trend is toward less coal globally, it is clear that the situation will improve from here.
The Union of Concerned Scientists report is focused on the United States, and concludes that electric vehicles produce less CO2 than typical conventional vehicles everywhere in the US
We found that: (1) driving the average electric vehicle
in any region of the country produces lower global warming emissions than the average new gasoline car achieving 29 MPG; (2) our ratings in 20 out of 26 regions have improved since our 2012 report; and (3) about 66 percent of Americans—up from 45 percent just three years ago—live in regions where power- ing an EV on the regional electricity grid produces lower global warming emissions than a 50 MPG gasoline car.