... submission to the laws of society (George Berkeley, 1712): "And since the bond and cement of society is submission to its laws, it plainly follows, that this duty hath an equal right with any other to be thought a law of nature."
... charity (Jonas Hanway, 1758): "As charity is the great bond of union, and the surest cement of society, the present occasion will warrant the greater indulgence."
... sympathy (Henry Home, 1758): "When we examine those particular passions, which, though painful, are yet accompanied with no aversion; we find that they are all of the social kind, arising from that eminent principle of sympathy, which is the cement of human society."
(Henry Home, 1758): "Nor must we judge of this principle as any way vitious or faulty: for besides that it is the great cement of human society, we ought to consider, that, as no state is exempt from misfortunes, mutual sympathy must greatly promote the security and happiness of mankind."
... sincerity (Henry Venn, 1763): "In these several important particulars, and in all similar to them, you will pay a conscientious regard to sincerity. Your motives also will be distinct from those of the mere moralist, and infinitely more cogent. He may be an advocate for truth and sincerity, and would have all men practice it, because it is the cement of society, and the only foundation of mutual confidence. Feeble motives, alas!"
... the ocean (James Hervey, 1779): "I am glad to find, that a jealousy for the interests of morality, is the chief obstacle in the way of your assent; because, I am persuaded, it is much of the same nature with those forbidding and mistaken apprehensions, which our ancestors entertained, concerning the ocean. They looked upon it as an insurmountable obstruction to universal society. Whereas it is, in fact, the very cement of society, the only means of accomplishing a general intercourse; and the great highway to all the nations of the earth."
... the illusion that secondary qualities are in external objects (Henry Home, 1779): "Now if this illusion be the only foundation of secondary qualities, they must be defined perceptions in the mind of man, which by an illusion of nature are placed upon external objects....In a word, this illusion is the cement of society, connecting men and things together in an amiable union."
... language (William Parker, 1781): "Communication of thoughts, of mutual counsel, and designs of action, was one original intent and main use of speech: and so language becomes one common bond and cement of society, and mutual connexion of men amongst each other."
... the administration of criminal and civil justice (Alexander Hamilton, 1787): "There is one transcendant advantage belonging to the province of the State governments, which alone suffices to place the matter in a clear and satisfactory light,--I mean the ordinary administration of criminal and civil justice....This great cement of society, which will diffuse itself almost wholly through the channels of the particular governments, independent of all other causes of influence, would insure them so decided an empire over their respective citizens as to render them at all times a complete counterpoise, and, not unfrequently, dangerous rivals to the power of the Union."
... opinion, i.e., public opinion (James Wilson, 1792?): "All trials, says Beccaria, should be public; that opinion, which is the best, or perhaps only, cement of society, may curb the authority of the powerful, and the passions of the judge; and that the people, inspired with courage, may say, "We are not slaves; we are protected by the laws."
... friendly confidence, i.e., trust between friends (Charles Johnstone, 1797): "The ingratitude and perfidy of one, whom he had placed his whole confidence in, and bound to him by the highest obligations, upbraid him continually with his own baseness to his patron, and make him afraid to place trust in any other; so that he lives in a state of constant suspicion and dread of all mankind, destitute of that friendly confidence, which is the cement of society, the comfort and support of life."
... fear (Plutarch, as translated by John and William Langhorne, 1804): "The Lacedaemonians have not only temples dedicated to Fear, but also to Death, to Laughter, and many of the passions. Nor do they pay homage to Fear, as one of the noxious and destroying demons, but they consider it as the best cement of society."
... just subordination (William Augustus Miles, 1808): "A respectful deference on the part of the people, to the judgment of those who are entrusted with the executive government, is necessary for the preservation of that just subordination which forms the very essence of all civil institutions, and constitutes the best cement of society."
... children (John Evans, 1810): "Cornelia turned the conversation to another subject, to wait the return of her sons, who were gone to school. When they returned, and entered their mother's apartment, she said to the Campanian lady,--These are my jewels, and the only ornaments I admire! Such ornaments, while they impart a refined gratification to parental affections, are the cement of society."
... love (Samuel Davies, 1811): "Love is the cement of society, and the source of social happiness; and without it the great community of the rational universe would dissolve, and men and angels would turn savages, and roam apart in barbarous solitude."
... small talk (North American Review, 1823): "But evil and good generally keep close to each other in this world of compensation, and the good caused by easy access to literature, is indubitable and important; the tone of small talk -- the great cement of society, is much elevated; better and higher things are made the subject of conversation; a lady or a gentleman must know more and think more than formerly; and this is all extremely well, for it is much better to discuss the last books than the latest scandals, however the change be effected."
... confidence, i.e., trust (John Rowan, 1826): "Confidence is the cement of society; it is the principle of its cohesion: and never, in that character, fails to perform its function."
... property (James Mackintosh, 1835): "Property, the nourisher of mankind, -- the incentive to industry, -- the cement of human society, -- will be in a perilous condition, if the people be taught to identify it with political abuse, and to deal with it as being involved in its impending fate."
... courtesy (Charles William Day, 1852): "Courtesy is the cement of society -- the philanthropic amalgam which blends the variations, and unites the trifling inequalities, of the great human family."
.. the middle class (John Bascom, 1875): "As midway men, they furnish the natural cement of society, they keep labor in countenance, and check the hauteur of capital."
... religion (Thomas Alfred Walker, 1899): "But religion is the cement of human society. Its utility is even greater in the larger society of mankind in general than in the limited society of any particular state, where its place is partly supplied by laws."
Some of the dates are almost certainly not right, but simply the earliest I could find without spending hours on the topic.