The main benefit of the international adapter kit offered by Apple is that the plugs actually snap on to the brick adapters used for all Apple devices. Once you get your ipod, you'll notice that one corner of its power adapter where the plug resides can come off. You can replace it then with the plug for another country. While not essential, it's quite nice when you have several Apple devices that can all make use of these different tips. ...not all at the same time though.
When in a country like South Africa, you could charge your iPod from a computer's firewire port. In fact, this method of charging is primarily how I charge my iPod everywhere. I never bring the wall adapter when traveling, because it's so easy just to plug it into my computer while working or using my car charger when driving.
As far as I can tell, there's no difference between tape adapters. They're probably all made at the same facility in Thaiwan, ShenZen or Singapore, where different companies have their labels stuck on them. Go with the cheapest, probably about $10.
Don't go with in-ear headphones for running. I don't think they'll stay in for that. Plus, it seems like you wouldn't want to keep out noises around you while running, which in-ear styles tend to do. I don't know what would be best... Maybe check out reviews on Amazon or some fitness sites.
For the full-sized iPods, they make these neoprene belt packs that are designed for use while running. The belt clips seem like they would kind of bounce around on your waistband as you run. But might as well try out what you already have, and if that doesn't work then research other options.
The output jack is a standard mini jack. You can get the Y dongle suggested by BP888. I experienced a problem with grounding when I did that though. Because the iPod wasn't grounded, I could hear a hum through the speakers when I played my iPod. While you don't need any special kit for hooking up your iPod to your stereo you will probably need something that takes care of that grounding issue. I'm sure there's a solution less than $39 out there.