I always use cotton rope for my dog toys. It's all natural and isn't a big deal if your dog swallows pieces of it. I get my rope from both Knot and Rope Supply and Amazon. Knot and Rope Supply sells cotton rope by the foot in a number of different sizes: http://knotandrope.com/store/pc/viewCategories.asp?idCategory=6
I also have ordered spools of rope from Koch on Amazon: http://amzn.to/15MFPY3
You'll want to get the right size rope for your dog. A 1/2"-3/4" rope would be suitable for a little dog, while 1.5" rope works for very large dogs.