It's hard to get firm proof of a Coraline in old records because of the natural confusion between that name and Caroline. Most of the examples of Coraline in the index to the US Censuses on Ancestry Library are probably mistakes for Caroline; however, it's also true that any real Coraline is probably even more likely to have been mistakenly recorded as a Caroline by census takers who were "assimilating" the unusual name they were told to one that they were familiar with.
I think I have finally found one, however. There is a woman who was born as Coraline Howell in Mississippi in 1876 who married Charles Bass and became Coraline Bass. They later moved to New Orleans. She is listed as Coraline in the 1900 Census of Hinds County, Mississippi and in the Social Security death index as dying in New Orleans in 1972. Though the indexes to the censuses of 1880 and 1920 list her as "Caroline", when I look at the actual census records it looks like the census taker wrote "Coraline" to me. The 1910 census taker did clearly list her as Caroline -- and the 1930 census, to make matters more confusing, lists the wife of Charles Bass as "Zilda". However, it looks to me like the preponderance of evidence is that this woman was indeed named Coraline.
Coraline is such an obvious blend of Caroline and Cora that it's hard for me to believe that there weren't others before Neil Gaiman who thought of it. Eventually other examples besides Coraline Bass will probably be verified, IMHO.
This message was edited by the author on April 4, 2009 at 4:35 PM