My partner didn't kick his coke-zero habit for about 10-12 months after going paleo - we got a Soda-Stream, and he used their version of coke-zero, and added less & less of the syrup over a period of time, and finally, he stopped after he'd been drinking 1/2 to 1/3 strength sodas for a few months, and had reduced the volume to just one glass with dinner. Up to that point, just missing a 'dose' would have given him a migraine. When he did finally stop, he didn't have any issues.
Now he drinks water only as his main beverage. He doesn't now, and has never drank, coffee or tea. He recently found that he really likes plain black tea Kombucha. The brand we like is Invisible Alchemy, and only the plain one. But this is limited to one 4 oz dose a day - nothing like the liters he drank of Coke Zero.