A workable solution
I am able to carry my headphones, sync cable, socket plug, and polishing cloth all in a case originally made to hold a Nintendo DS portable. The overall dimensions of the case are only slightly larger than an iPhone case.
It's a hard case with one side with a net to hold the plug and sync cable. The other side I can put my headphones without having to roll them too tight where they begin to tangle. It has a zipper that goes almost all the way around which allows me to lay it open completely flat.
Cost me $10 at Fry's and I carry it in my briefcase bag along with my iPhone. It's also great to have everything with me most of the time so I don't have to worry about battery life since I can recharge at home or work.