When is café used and when is coffee shop used? Are there any differences? Which is more widespread?
From personal experience in the United States, a café serves meals, while a coffee shop usually just sells snacks (muffins, scones, shortbread). This is not strictly the case, and both usually serve coffee.
Side note; I would almost argue that a coffee shop carries the pretentious connotation more than a café, since coffee shops are where people usually go to study, write, or work on a laptop and time appears more important.
COCA has 1383 instances of coffee shop; a search for café is actually converted into a search for caf, giving 2069 hits of which most appear from context to be café, although not even all of those are in the sense of cafeteria — e.g. some are café con leche. Cafe without the accent has 7376 hits, and cafeteria in full has 2780. So overall, coffee shop appears to be outnumbered on the order of 10 to 1.
I can't comment on American connotations of café vs coffee shop, but one of the examples caught my eye:
Where: The Midnight Rooster, a gritty little coffee shop and cafe in Hartsville, South Carolina
This could be a merism or it could indicate that the author considers those to be two halves of a single business.
(Also, although another answer claims that café has a connotation of being either classy or pretentious, the presence in COCA of a few references to a truck stop café suggests that this connotation is not universal).