I am descended from the John Cunningham you are talking about, but via a previous wife whose name I don't know.
You listed the children as John, Asa, Thomas, Benjamin, Martha, Jessey, Louis, Delia, Hariette, Ruben, and Effie. There is one older son, Jerry, born in Alabama about 1857. Jerry is not listed in John and Mary's household on the 1880 Garland Co., Arkansas census because by that time Jerry had already moved out and started a family of his own. He is living with his wife Ellen and son James a few census pages down from John and Mary.
John and Mary were on the 1870 Scottsboro, Jackson Co., Alabama census, though there John gave his name as James. His full name may be John James or James John. That census lists Jerry as the eldest son, along the three other children who were born by that time (John, Asa, and Thomas).
Jerry and Ellen's son, James Oliver Cunningham, was my gg-grandfather. They also had a daughter, Sarah E. Cunningham, who married Jesse M. Canada. I can give you more information on this line if you're interested.
Because Mary would have only been 9 years old when Jerry was born, John/James must have been married before, as you suspected. The next three children (John, Asa, and Thomas) should also be from John/James' first marriage, whereas the others are Mary's.
I haven't been able to find John/James' parents, but I believe he had a younger brother, Rev. Thomas J. Cunningham, who was living near John/James on both the 1870 and 1880 censuses. Thomas J. was born in 1843 in Alabama, married a Mary Jane Unknown in Jackson Co., Alabama in 1866, died in 1900 in Garland Co., and is buried in Lowe Cemetery with his wife and several children.
Feel free to e-mail me if you'd like to exchange more info.