Hm... I don't really know.
My logic is that non-rhotic dialects must have developed or become widespread in England after the future-Americans left, because that's why the R is preserved elsewhere, and also because I remember hearing that in many ways the American accent is actually more representative of earlier English (like Shakespeare). [I don't know how accurate that is in the big picture, but I do think it applies to R.]
So given the approximately 400 year timeline, I assume it developed later. Areas still connected to England a little longer, like Boston, also end up with some effects of this.
Searching a bit comes up with a few results:
http://www.oxfordhandbooks.com/view/10.1093/oxfordhb/9780199922765.001.0001/oxfordhb-9780199922765-e-63/r/-sandhi is a very technical term that appears to cover this, to re-answer the original question better than my last post.
For development, this Wikipedia article actually does a good job:
http://en.wikipedia.org/wiki/Rhotic_and_non-rhotic_accents#Development_of_non-rhotic_accentsThat page mentions some other languages also. Word-final R in German, for example, is more or less not pronounced (it becomes a vowel that colors the preceding vowel).
That leads to the "intrustive R" page:
http://en.wikipedia.org/wiki/Linking_and_intrusive_RNo clear answer on how early it developed, but that page seems to suggest it's fairly recently (1900s?) becoming widespread.