You're confusing several different effects. Modern portland cement is made in a kiln and is essentially a synthetic production of what was found coming from a volcano. But the components are carefully assayed and the process carefully controlled, so it will be better than the wild stuff and always consistent in its properties.
What makes surviving Roman concrete particularly good is that besides large rocks, small rocks, sand, etc. as aggregate, they added super fine dust which fills the pores that would form without them. So their souce of volcanic flyash did that without being done on purpose…they just found that it worked.
So are you wanting a pozzolan that is far superior to quicklime in gluing the bits of aggregate together and being weatherproof in comparison to plain calcium hydroxide? Or do you mean finding the right mix of aggregate sizes including ultra-silt to produce a more waterproof result, so it lasts much longer as water doesn't move through its pores?
To make a super concrete, they would need to figure out both of these issues. Now cement that is immediatly superior to common stuff (portland cement vs plaster of paris in modern terms) is obvious to notice in the short term. Finding additives and subtle mixes of aggregate proportions to make the set concrete harder is hard to tell without more modern instruments, and longterm wear—how can they tell that this recipe will last 100 years vs 20 for harbor footings?
For the better cement, here are some natural materials that might work the same. For the blend of aggregate and filler, anything will do: they just need to find or produce ultra-fine silt and include the right proportions.
The question becomes why would they think to do that or how did they stumble upon it accidently? One answer might be from the making of fine porcelain where a smooth grain is desired. Look at bone china where the minerals are ground and reground to heroic ends. Maybe they got the idea to manipulate the building material in the same way, after seeing that the statues outside the temple stood weather better than the foundation.
See also: The Roman Pantheon: The Triumph of Concrete
Research by David Moore, P.E.. Maybe it will give you some ideas for alternatives, as well as providing more authorative information on just why it was so long lasting.