It might help if you do it in stages. And it will be the developers who create this, the host probably won't have anything to do with it unless they work on your actual site code.
For example, for my Magento client, we have some products that are really easy - just a widget, no attributes, colors or sizes. But we have some items that are a lot more complicated, with lots of options, attributes and add-ons. (And none of them really conformed to Google's categories, so we had to kind of extrapolate)
So we started with just the simplest products first, and wrote a feed for that. Once we got that working and accepted, we starting banging away on the more complicated stuff. And there are some products we'll probably never be able to shoehorn into Google's system, but that doesn't mean we can't do the best we can.
So start with half a dozen of your simplest products, and make a sample feed. You shouldn't have to put ALL the products in - you're just telling them what you want the finished feed to look like.
Also send them to this link:
What they'll be doing is pulling the product data out of your database, and adding the various Google requirements to make a working feed.
Have them generate a small test feed for you and give you the file, and then submit it manually to make sure it works okay. Once you get one that's accepted and working, you can work on the scheduling.
Next tell them that you want to be able to have this feed generated on a scheduled basis (you can tell them to generate it daily if you want, but Google will only pick it up once a week. If you want to submit it daily, you'll have to submit it manually) They should be able to use cron (that's the scheduling program on the server) to generate the file. Then you can tell Google to come pick it up every week, or you can submit it yourself.
Once you get your first products up and running, you have the basic technology in place, and then you start working on your more complicated products.
I can't help you with the countries; all my stuff is US only.