The only thing I've ever quit cold turkey in my life was sugar in tea and coffee. Maybe a rip the band aid off approach?
My husband really likes his sodas. He's been gradually cutting back. He went to some of those lightly sweetened teas, and now the totally unsweetened kind--which he doesn't really like. He does like Pellegrino and the flavored Perrier waters as a soda substitute. If you can find Gerolsteiner it has a pleasant almost salty mineral taste.