My experience with diceless games is almost exclusively with Microscope RPG, but it's an excellent way to demonstrate diceless roleplaying. Never have I heard the complaint (before or after a game) that Microscope has no dice—though I've often heard people exclaim in pleased surprise, after the fact, that they didn't even notice the lack of dice at the time. Most of the time, the lack of dice is completely overlooked.
You could play a session of Microscope—it's an excellent game in its own right and, for some reason I don't adequately understand, is extremely accessible even to the most traditional groups—but that might not be necessary. The insight that Microscope gives me into how a game can still feel "right" without dice might be enough for you to convince them to try diceless...
Unpredictability is key, not randomness
In Microscope, the sense of not knowing what's going to happen next is provided by the simple fact that humans are unpredictable, and your fellow players are human. You never really know what your fellow players are going to do next, even when you could make a good guess. There are rules that constrain their choices, but which still leave the range of possibility pretty wide open. Flipped around, the constraints on your choices when it's your turn channel your creativity into specific directions, significantly reducing the "decision paralysis" that complete freedom can cause, while still giving you significant freedom in how to proceed.
So being around four or so other humans' brains is the randomising element. Out of the distributed decision-making comes a mix of predictability and unpredictability, which is exactly what dice are for in most dice-full games.
Explain that, and maybe your players will be able to imagine something a little more varied and interesting than playing the "GM storytime" that they're probably imagining and recoiling from.
And of course, you could always play a round of Microscope to break the ice. I have never yet had someone to shy away from it, including the most traditional players I know. It helps that it involves no more commitment or prep than a boardgame, making it an even easier sell.