Concrete is a composite of cement a binding agent and another material that provides the soft cement durability. For durability the key factor is maximizing the binding surface area between the cement and the additive.
The first step is selecting an additive with large surface area. Romans used volcanic ash, the example in Cort Ammons answer fly ash. The function is the same, to increase the surface area the cement has to attach to. Generally "ash" is good since the properties that make us call something "ash" imply large surface area to mass ratio. (Most other things on your list are not that good as they have grains that either are worn round, have smooth surfaces, or both.)
The second step is to optimize the ratio of cement to additive (almost certainly wrong term), cement is soft so if you have too much of it, the concrete will have bad mechanical properties. If you think about it, maximizing the cement to additive surface area means having the right ratio so that weak additive to additive contacts are avoided and that the amount of soft cement mass not in contact with additive is avoided.
But it is not really this simple in practice, obviously. You have to also think about economics and the intended purpose and the types of loads on the structure. Large rocks with low surface to volume ratio almost always weaken the structure, but they can drop the cost without significant weakening if the concrete is only exposed to compression. The concrete around the rocks will still be weaker and crack, but cracked concrete still can carry weight if it can't move.
A related issue is that if you want the concrete to have specific properties at scales much larger than the grain size of the additive, and cube-square law implies the additive should have small grain volume for optimal durability, you might want to, or even need to, use reinforcement. Reinforcement generally reduces long term durability due to stresses in the interfaces between the concrete and reinforcement and steel, for example, also corrodes. But people have been using glass or obsidian fiber reinforcement, which might be stable over long time.
And of course if you want long life you also need to consider chemical stability. Usually this isn't an issue or the actual issues are hard to predict. For example Roman concrete is still vulnerable to damage caused by pollution that did not even exist when the buildings were built. Nobody blames the Roman architects for that oversight. (Although since you have "manure" on the list, you should remember that organic components or most cheap metals degrade over time and cause the entire composite to fail when doing so.)