A species of coffee from Cameroon is caffeine free.
Read about it here http://species.asu.edu/2009_species09 where it was named one of the top 10 new species of 2009 (named in 2008) by the
International Institute for Species Exploration at Arizona State University.
Coffee and Conservation report that the plant was was “first collected in 1983, but remained unstudied and not described to science until 2008” in their post.
Stoffelen, P., M. Noirot, E. Couturon & F. Anthony. 2008. A new caffeine-free coffee from Cameroon. Botanical Journal of the Linnean Society 158: 67-72.
OSU campus-based folks can see the full text of the paper via this link http://www3.interscience.wiley.com/journal/121394905/abstract
ABSTRACT
“A new Coffea species from Cameroon is described and compared with the other species of Central Africa. Coffea charrieriana Stoff. & F. Anthony can be recognized easily using morphological characters of leaves, flowers and fruits. Moreover, it is the first record of a caffeine-free Coffea species for Central Africa and only the second report for the African continent. Cameroon is one of the three centres of diversity for the genus Coffea, showing a similar number of species to that of Tanzania. © 2008 The Linnean Society of London, Botanical Journal of the Linnean Society, 2008, 158, 67–72″.
It seems that caffeine free coffee species are rare. I don’t know how long it takes to breed new coffee varieties, but i am sure someone is working on getting the caffeine-free trait into a cultivatable form. Stay tuned.
As a dedicated caffeine devotee I vote that the new variety should be called “What’s the point?” in honor of the no-fat decaf latte.

OSU
I´ve been around, but i´ve never heard of natural caffeine free coffee.