Testament of Joseph 19 (c. 2nd century BC) predicts that the Messiah will be born of a virgin.
Testament of Joseph 19:8-9 (trans. H. C. Kee) in The Old Testament Pseudepigrapha, ed. James H. Charlesworth (2 vols.; New York, Yale University Press: 1983), 1:824
8 And I saw that a virgin was born from Judah, wearing a linen stole; and from her was born a spotless lamb. At his left there was something like a lion, and all the wild animals rushed against him, but the lamb conquered them, and destroyed them, trampling them underfoot.
9 And the angels and mankind and all the earth rejoiced over him.
Recension A (ibid.) reads:
And I saw in the midst of the horns a certain virgin wearing a multicolored stole; from her came forth a lamb. Rushing from the left were all sorts of wild animals and reptiles, and the lamb conquered them.
Because of him the bull rejoiced and the cow and the stags were also glad with them.