Prior to the development of the な particle (presumably from なる) several hundred years ago, what constructions were used where な-construtions are currently used? E.g. in the phase きれいな女, would that have been きれいの女, 女のきれい, きれい女 (and would that be kireionna or kirei onna?), きれいなる女 or something else?
It is from なる, in a way; but it may not be the one you're thinking of. The なる here is the 連体形 of the former copula なり, which itself derives from に+あり (modern ある). This seems to have been the copula as far back as we have records of. Indeed, this kind of adjective is younger than the copula it uses - these kinds of adjectives do not occur before the Heian-jidai.
A couple of forms do appear that have since become them (e.g. adjectives ending in -らか), but I don't know how these were used - my source (Bentley's Descriptive Grammar of Old Japanese Prose) mentions their existence, but only says that these なり-based adjectives are new as of the Heian-jidai; it says nothing at all about how they were used in Old Japanese. I would speculate that they're used in the very old adjective patterns that require no morphology at all: so just like you can get /awo sora/ (/səra/?) where you would expect /awo-ki sora/, I bet you could get /tapiraka umi/ when later you would expect /taɸiraka=naru umi/ (for 平らかな海).
As for きれい, it's a Chinese loanword, and was loaned after the creation of these kinds of adjectives. So there was never a point in time before きれいなる女 - you would have used a native Japanese word like 美しい, and so you would have either /utukusi-ki womina/ or the older /utukusi womina/.