Apologies for this - where have you seen John's birthplace as Cowhill, Gloucestershire?
I am assuming that it is the 1871 census return - RG10/2587 folio 53 page 2
John - 29 - Ag Lab
Ann - 28
Harriett - 6
Ellen - 4
Frank - 2
I've looked at the birth registrations for Harriett, Ellen and (William) Frank in the Thornbury Registration District - mother's maiden name for Harriett is Monday and Ellen is Mundy. And there is a marriage entry, in Thornbury RD in 1863 where John Cole and Ann Mundy appear on the same page.
26 September 1863 - Thornbury
John Coles - 21, bachelor, Labourer. Father: Charles, Labourer
Ann Mundy - 21, spinster. Father: George, Labourer
Witnesses: George and Emma Mundy
Added: Frank's birth registration is also with mmn = Mundy, and there is a James Alfred born 1871.