Do what downtown Vancouver, BC did - take out a travel lane and/or parking spots and create dedicated bike lane.
Sure, some businesses complain, but overall number of bikes on the road seems to have increased.
https://cyclingmagazine.ca/sections/news/opposition-to-propo...
http://dailyhive.com/vancouver/mobi-bike-share-vancouver-rid...