According to New World Encyclopedia people may have showed some awareness of the duality already in prehistoric times:
"Stones carved in shapes showing the symmetries of various polyhedra have been found in Scotland and may be as much a 4,000 years old. These stones show not only the form of various symmetrical polyhedra, but also the relations of duality amongst some of them (that is, that the centers of the faces of the cube gives the vertices of an octahedron, and so on). Examples of these stones are on display in the John Evans room of the Ashmolean Museum at Oxford University." However, as Marius Kempe pointed out, the stones in question were altered to look more like Platonic solids. And even interpreting "polyhedron" loosely icosahedron is still missing among them:"while the
symmetry of some of the Platonic solids is present, these are not polyhedra... no balls with twenty knobs have icosahedral symmetry. Many of the carved stone balls have six knobs, and thus have approximate octahedral symmetry in their knob placement. Some have four knobs and tetrahedral symmetry." While duality is not restricted to Platonic solids, and some idea of it is possible without icosahedron, it is unclear what exactly "relations of duality amongst some of them" refers to.
There are differing accounts on whether Greeks knew of all five regular polyhedra before Theaetetus. But even for Theaetetus the duality, if he noticed it, was likely little more than an afterthought or a curious fact rather than a construction/principle. When Archimedes later discovered semi-regular polyhedra, a.k.a. Archimedean solids, as far as we know neither he, nor anybody else for over two thousand years thought to swap their faces and vertices and see what happens. There was so little interest in polyhedra that the work of Archimedes did not survive the middle ages, and we only know of it from a mention in Pappus's Collection. Only in 1430 Paolo Uccello depicted two new (non-convex) regular polyhedra in a mosaic on the floor of San Marco cathedral in Venice, and Kepler described them mathematically only in 1619 Harmonices Mundi, two more were found by Poinsot in 1809. But again neither Kepler nor Poinsot made any use of duality.
The first use of duality as a principle appears to be in Catalan's Memoire sur la Theorie des Polyedres of 1865, where he constructed the duals to Archimedean solids, and noted that they are not semi-regular (faces are not regular polygons). These are now called Catalan solids. And only Brückner in his classic 1900 textbook Vielecke und Vielflache: Theorie und Geschichte, that summarized everything known about polyhedra at the time, defines what we refer to as "duality" explicitly. George Hart assembled annotated bibliography on polyhedra that may be useful for further digging.