I expect that you were downvoted because the StackOverflow community likes people who have a go at solving their problem, do a bit or research and thinking about their problem and then ask a question that can be answered in a couple of paragraphs.
Asking a question like "somebody asked me to do this, and instead of thinking about how I might attempt it, I just came here" gets you downvoted.
You can do this in MapKit, by tracing all the countries and recreating their polygons using MKPolygons, but it's going to be a difficult manual process to get that polygon data.
What may be easier is to find a vector map of the world from a stock art site, then in Photoshop, cut out each country and export it as separate green bitmaps with transparent backgrounds, so you have a separate image for each country and a separate background image with all the countries in red.
Then in your app, you put your map image in a UIScrollview with zooming enabled. If you need to zoom really far the you'll need to use a CATiledLayer and chop up the images even more, but for your purposes you can probably get away with a big image that's about 2 - 3 x the size of the iPhone screen.
When a country has a new shop in it, you'll need to compare the position of that shop against the country image position on the map (probable easiest to just keep an internal dictionary of shops against country rather than trying to calculate this from their GPS position on the fly) and draw the appropriate green image inside the scrollview in from of the map.
Then when you zoom in, draw your shops as small images at the correct positions on the map. Again, you'll need to go through manually and work out what all those positions will be and store it in a Plist or something.
Obviously each step of doing this could be a StackOverflow question in its own right, but try it and see where you get stuck, and then come back and ask more questions.