In general, solids are made from from atoms that originate naturally in stellar nucleosynthesis,
see for example the composition of our sun's atmosphere from an older paper of
Asplund et al (2005):

Here you see for example, that silicon (Si), an important rock-forming element, has an abundance relative to hydrogen of $10^{-3}$, or for every 1000 hydrogen atoms there is one silicon atom. Also we find lots of oxygen, carbon, magnesium, iron,... all known rock-forming elements.
The above work has been performed using spectroscopy, and in a similar way we can detect solids in space mainly through three means:
Spectroscopy (again): Small particles of $\mu m$-sizes exist in vast numbers in the spectrae of red giants (I'll comment on the formation later), white Dwarves, in cold molecular clouds and even in far away Quasars. Those numbers are so huge that we can detect prominent features like the 10 $\mu m$-feature of the $Si-O$ bond that we find in many earthly minerals. See also the following example of a clear detection of silicate minerals in the envelope of a young star (the broad trough at 10 $\mu m$) (c)Uni Hawaii:

As mentioned, when solids grow, their numbers diminish. Thus big solids around the sizes of mm become invisible in spectrae, but sometimes can be detected through scattered light, as they undergo Mie-scattering with visible or infrared light when being very near to a stellar source.
Then one can take pictures like the one from Benisty et al. 2015 of the young stellar system MWC758, where we see dust spirals possibly caused by the existence of young planets:

Reflection of solar light: As solids grow to cm, meter, kilometer-sizes they become invisible for the above methods. Only at sizes of tens to hundreds of kilometers and only in our solar system can we then detect them again through the reflection of solar light.
Now that we have established that solids exist in space, let us review the theoretical perspective of growth mechanisms:
- dust of up to $\mu m$ condenses out in the relatively cool atmospheres of red giants (AGB stars), where the ionized environment helps to grow solids through charge separation. Details e.e. in here.
- this dust is blown away in the strong AGB star winds into the interstellar medium, where it helps to create new star systems (see also the second image I linked).
- All successive growth to larger sizes has to happen in the interaction with gas, thus it usually happens in the relatively dense environment around young stars
- The dust has now to overcome the bouncing barrier in order to grow into cm to meter-sized particles that we call 'pebbles'. How particles overcome this barrier is unclear in general, but the article I've linked mentions a few solutions.
- Pebbles are defined by their property that they interact with the orbiting gas in protoplanetary discs through friction. This interaction allows them to trigger the streaming instability, a very efficient mechanism that is able to compress clumps of pebbles directly into km-sized solids.
- Now small comets grow through direct collisions, up to planetary sizes. Only in this stage geological mechanisms can play a role, like the igneous separation of minerals that you've mentioned.
That's it for now. I think with this description it is clear that the whole problem is not chicken-and-egg, but if you think otherwise then please comment.