The world which I am working on is set in the far future on a colonized/terraformed planet that has become reduced to a medieval-like level of technology. It was not previously inhabited by any life, and thus has no fossil record and no limestone. Lime-based mortar has been used for thousands of years, and thus is very important for the construction of large stone buildings. Does this mean having large stone architecture in a world without limestone is impossible? If the calcium carbonate is present on the planet but not stored in limestone, would it be accessible and usable in other ways? Are there alternatives to lime that could be used as mortar?
Tufa and travertine
Heat them. They're a perfect limestone replacement, and exactly what you need. If you have pozzolanic soil, there's no reason you can't do better than mortar and make cement, exactly as the Romans did.
Note that travertine can be produced directly from ultramafic rock without any biogenic limestone playing a part.
Mortars made out of clay were widely used in places where clay was abundant and lime or limestone hard to come by. The linked article has a lot of stuff on clay mortars as used in Scotland.
Lime is generally considered to be the most common mortar material for traditional structures, yet in many parts of Scotland, especially areas where clay-rich soils are common, clay was commonly used as a mortar in masonry building. Sometimes seen as an archaic and purely vernacular tradition, clay mortars were in fact used up until the end of the 19th century and possibly later in some locations. A suitable mortar should contain heavy clay from a silicate-rich soil that can bind the matrix of the mortar together and support the compression loads of the masonry. Such material, normally found below the topsoil layer, was dug out of the ground and sometimes used directly for bedding the masonry and filling the wall core, or mixed with aggregates and straw to form a mortar.
Clay is a product of weathered stone. There should be clay on a planet with a hydrologic cycle. Maybe even more clay because there will be more erosion and weathering without surface plant life to limit it. And maybe better clay omn your world because the components of topsoil that make it good for life (e.g. organic matter) make it worse as mortar. On this lifeless world, weathered surface soils might be suitable for use as clay mortar and so people would not have to dig for subsoil.
Sea shells are one of many other ways to make quicklime.
you can roast sea shells in the same way you cook limestone and get the same results. Tabby concrete is made this way and it is what early Spanish settlers used in the new world, since they were in coastal areas with no limestone. Human settlements can generate a LOT of sea shells so supply is not a huge issue. Plus of course they can always farm shellfish for the shells with a bonus of food.
As Sean OConner have pointed out you can do the same thing with travertine a non-biological mineral found around hot springs. There are several other minerals mentioned in other posts that will work as well. You can even use eggshells, anything made of calcium carbonate will work.
Mortar is not required; It just makes things easier. Interlocking bricks can be used and the construction method is formally known as "dry stone" and is older than mortar and makes for more durable walls. There is debate about the construction methods used such as cutting, poured/molded, or re-formed.
One example are the Incas at Saksaywaman in Peru:
I seem to remember there also being walls somewhere that literally look like your typical puzzle piece blocks, complete with interlocking circular tabs and slots. But I can't remember the location. I thought it was Gobele Tepe but apparently it's not. If anyone remembers, please tell me so I can post it.
Alkali based mortars and cements
If we ignore CaCO3 altogether:
Yes,using aluminosilicate geopolymers/alkali activated cements.
You can make cements using sodium or potassium hydroxide, and an amorphous aluminosilicate mix, such as certain pozzolanic soils, flyash, dehydrated clays, geothermal silica, etc. Obviously, it'll be much more costly than Portland cement or lime mortar as alkali hydroxides are comparatively scarce. Nonetheless, it's possible.
If you had adjacent deposits of natron and kaolinite, you'd be well on your way. It could be discovered as a side product of a porcelain making operation.
Another alternative for indoors only is bonding things with sodium silicate (waterglass), which you can make from sodium hydroxide and geothermal silica. You just mix up any powder in it and it sets. It is insanely, incredibly hard and strong...BUT it is attacked by water, so can only be used in a completely dry environment, which is why it's not used everywhere.
It is possible to make cement without limestone. If it is just that limestone is missing then aragonite or calcite could be used. If something a little different is needed try dolomite CaMg(CO3)2 or even Magnesium carbonate.
With sufficient heat they will all decompose to reactive oxides that could be used in cement.
Sulfur can be used as binder to make concrete and mortar. The recipe is 20%-32% molten sulfur; 10%-20% fine silica, mica and carbon filler; and rest rock aggregate.
- Strength and Durability of Sulfur Mortar: https://trid.trb.org/view/354103
- Preparation of Sulfur Mortar from Modified Sulfur: