That's why you start small, and work up incrementally. Bike lanes are the first step: just make it possible. Next is paths that cut across town to allow bikes (and pedestrians) to avoid roads altogether. Just put them in wherever you can. Eventually you can start connecting them, and gradually it starts to make sense to say "let's just walk there" or "I'll meet you there on my bike."

It's literally just paint and gravel, and micro zoning. But it helps every step of the way, and it adds up quickly.