PVA Glues
Depending on what you read PVA glues (usually what you see as white or yellow glues) are considered biodegradable. Elmer's is mentioned in this conversation but I didn't find anything official from the manufacturer claiming it as biodegradable. It should break down in water but PVA glue is based on a synthetic petroleum based polymer so likely this isn't exactly what your going for
Animal/Hide Glue
[S]hould be as much biodegradable and natural as possible
Choice of words leads me to believe you are looking for something else anyway so I would like to introduce you to hide/animal glue. The names are considered synonyms where this glue is concerned.
Hide glue is an adhesive made out of the connective tissues, bones and hides of animals
It is one of the earliest known glues in existence. Today it is predominately used in wood working but does have other applications.
In France, there is proof the Neanderthal used glue in their paint so that the cave paintings were protected somewhat from moisture. Animal glues from things like horse teeth can be dated back 6000 years.
nordicneedle.net
Note all hide glues are the same. There are hot and liquid versions and many individual variations sold commercially. I am speaking more of the hot glues that are sold as pellets and you have to melt them before use (Some liquids are mixed with other substances. Not all are except from your criteria though). Hide glue has a good set of features and some drawbacks depending on how your application
Number one being that it is non-toxic. It is a forgiving glue as you can reheat it once it has set to move or adjust what you are making or repairing in some cases. Since it is made from animal proprieties it is biodegradable. Its sets rather quickly which can be both a pro and a con. One major draw back is that it is water soluble and affected by humidity so this is not for outdoor use which may be a draw back here given your pictures. Some also have an off putting odor but that can be very subjective.
Hide glues is a rather engrossing subject and we are only glazing the surface here but I thought it was good enough to at least suggest. You can read more about its use in wood working (mostly to understand the process) you can read more at LeeValley. There is also a manufacturer that praises itself on its eco-friendly hide glues.