fruit- dried, fresh, in jam, cans, those little lunchpack ones in jelly (which is often carragean gum, not gelatine) juices. or make your own treats. freeze bananas and put them in the food processor for instant icecream, or make smoothies by blending them with ricemilk.
i don't know if you'd have sugar cravings if you haven't had sugary sweets in a good while. its normally been a short term thing for me, after a couple of weeks sugar-free i get over it.
its most likely you're getting sugar in other places anyway- sweetened soya milk, breakfast cereal, bread, regular peanut butter, canned beans and corn, jars of pasta sauce... loads of things you wouldn't expect to, often have scary amounts of processed sugar in them.
if you're craving sugar, just eat sweet stuff. just don't go nuts on it.