Personally, I'd just go with ordinary yellow wood glue even though it's synthetic. Natural things are not necessarily non-toxic, artificial things are not necessarily harmful, and PVA glue is pretty safe provided you don't drink the stuff (I wouldn't drink most hide glues either, and those were the normal glues used for woodworking before the advent of synthetics). Even melamine is only moderately toxic (as in, you don't want to eat it or inhale the dust, but a desk surface isn't dangerous unless it's breaking down).
I suppose the ultimate in non-toxic glues is unflavoured gelatin from the grocery store (essentially food-grade hide glue), but its adhesive properties have a reputation for being highly variable—after all, it isn't meant to be used as glue, so there's no QA applied for that property.