Asphalt concrete is similar to modern and Roman concrete (and tabby) in that hard cheap materials (pebbles and stones, or shells) are held into a firm shape by a binder. For concrete and tabby the binder is cement of one sort or another.
For asphalt concrete the binder is asphalt, or bitumen. This is a naturally occurring petrochemical which can be heated to softness or even liquid state and then will turn solid on cooling, trapping the stone aggregate in a matrix. Asphalt is naturally waterproof and largely impervious to microbial degradation.
Asphalt, also known as bitumen (UK: /ˈbɪtjʊmɪn/, US: /bɪˈtjuːmən,
baɪ-/),1 is a sticky, black, highly viscous liquid or semi-solid
form of petroleum. It may be found in natural deposits or may be a
refined product, and is classed as a pitch... The primary use (70%) of
asphalt is in road construction, where it is used as the glue or
binder mixed with aggregate particles to create asphalt concrete. Its
other main uses are for bituminous waterproofing products, including
production of roofing felt and for sealing flat roofs.
Modern uses of asphalt is almost all in the form of roads, and in this application asphalt concrete is probably superior to competitors. For buildings asphalt historically has been used mostly as a mortar, adhesive, or final waterproofing dressing. I think this is because asphalt is an uncommon natural commodity and more expensive than cut stone, brick or concrete. In the modern era, structural use of asphalt concrete is used to build dams where it can be poured in place like concrete but outperforms concrete in withstanding the structural stresses on a dam.
I am still not clear for this question if the OP wants materials that could have been used by preindustrial societies or actually were used. In case it is the latter, here is Herotodus around 450 BC describing the use of asphalt (aka bitumen) cement in building the walls of Babylon.
Further, I must show where the earth was used as it was taken from the
fosse and in what manner the wall was wrought. As they dug the fosse,
they made bricks of the earth which was carried out of the place they
dug, and when they had moulded bricks enough they baked them in ovens;
then using hot bitumen for cement and interposing layers of wattled
reeds at every thirtieth course of bricks, they built first the border
of the fosse and then the wall itself in the same fashion. On the top,
along the edges of the wall, they built houses of a single chamber,
facing each other, with space enough between for the driving of a
four-horse chariot. There are an hundred gates in the circle of the
wall, all of bronze, with posts and lintels of the same. There is
another city, called Is, eight days' journey from Babylon, where is a
little river, also named Is, a tributary stream of the river
Euphrates; from the source of this river Is rise with the water many
gouts of bitumen; and from thence the bitumen was brought for the wall
It is an interesting idea: asphalt concrete as a competitor with wood or brick or concrete. Especially in our current time when these conventional materials for making buildings are inexplicably scarce and expensive - asphalt has not risen in price in the same way (thought I think is still substantially more expensive). I searched for a freestanding structure made of asphalt concrete block but came up empty. Anyone who can find an image of such a building please add it in here!
I am fascinated by tar balls. Maybe in this world there is a beach with offshore petroleum seeps and the people gather the tar balls for use in making asphalt concrete.