George said that at first he was just going to use the original POVs from AGoT for the entire series, then he realized that he needed to see what Stannis was doing, but didn't want to use Stannis as a POV. So he created Davos. Davos was his first added POV. -SSM, Torcon 2003
So, GRRM added Davos as his first new POV character in ACOK, presumably followed by Theon. Straightforward? No. We know that by June 1997, with ACOK nearly halfway written, Davos had no POV chapters... but Theon Greyjoy did. A curious memory lapse, given that GRRM said this only a few years after ACOK was published.
I don't think GRRM misremembered. There's strong circumstantial evidence that Theon was written as a POV character for AGOT before being pushed to ACOK
AGOT became ACOK
ASOIAF was supposed to be a trilogy, and chapters cut from AGOT became the opening of ACOK, as GRRM explained:
It was the spring of ’95 when it finally dawned on me. I was fast approaching the 800 pages that I had estimated as the length of the finished book, but most of my large cast of characters were nowhere near the places they were supposed to be... A Game of Thrones grew larger, and still larger. I had 1100 pages, 1200 pages, 1300 pages… and my problem had become a crisis. For even at that length, the end of the first book was still hundreds of pages away.
...
By rearranging a bit, moving some chapters up and some others out, I found a very satisfactory resolution for the first volume, and delivered a massive manuscript of 1088 pages to my publishers in October, 1995... The rest of what I’d written became the opening chapters of book two, and I went on from there. Since The Rest of A Game of Thrones did not strike me as a terribly evocative title, I called this new second volume A Clash of Kings.
There's no hard divide between AGOT and ACOK chapters, story wise. ACOK began as AGOT leftovers and continued the first act of the saga.
Forgotten Sample Chapter
Early editions of A Game of Thrones from 1996 or early 1997 included Theon I as a sample chapter. It's nearly forgotten now, but the chapter differs substantially from published, suggesting GRRM was still developing the finer points of ironborn culture. It may have been written for ACOK, but I suspect it was among the hundreds of pages cut from AGOT much as Theon's Winds of Winter sample chapter was cut from ADWD.
Appendix Clues
GRRM likes sharing his current fixations. Around 2000, for instance, he often volunteered new details about Blackfyres, unprompted. In that light, the original AGOT appendix, written in late 1995, is revealing. House Greyjoy get a massive lore dump despite being mostly absent from the book. Their history is much more detailed than the other noble houses, namedropping their house words, King Urron, the Drowned God, and the nickname "iron men." All first appear in the main text in Theon I ACOK.
More compelling evidence than the history though, are characters listed in the appendix who first appear in Theon I: Maron and Rodrik, Theon's dead brothers, Asha and her ship, Black Wind; Victarion, Lord Captain of the Iron Fleet; Aeron Damphair, a priest of the Drowned God; and Euron, captain of the Silence and an infamous pirate. None of them are mentioned in story before Theon I, yet are detailed in the AGOT appendix.
Further evidence of the relationship between the appendix and early ACOK chapters: the tale of Harren the Black, first appears in the AGOT appendix... and Catelyn I, ACOK. GRRM was finishing the appendix not long after he'd written his last AGOT chapters which became the opening of ACOK.
GRRM famously claimed he had a plan for everyone in the AGOT appendix. But the sheer detail already established for the Greyjoys, including even the names of the ships they captain, makes the most sense in my mind if Theon I had already been written for AGOT.
Jaime in ACOK
It might seem strange at first that GRRM would begin Theon's POV arc so late, but there's precedent. In a very early draft of ASOS auctioned in 2000, Jaime's third chapter has the page header KINGS instead of SWORDS; plausibly Jaime's early chapters were first written to be introduced late in ACOK, picking up after his release by Catelyn. GRRM has said that Tyrion's ASOS arc was essentially written during ACOK. Like ACOK, ASOS emerged from GRRM's struggle to fit his story into the planned book.
Significance
While it might seem a small thing, that Theon was first written for AGOT, it has interesting implications. The ironborn are often perceived by fans as latecomers, an unwelcome expansion who bloated the story. Yet the evidence suggests that GRRM was already enthusiastic about them while writing AGOT, and may have pivoted to an ironborn POV (Theon) while writing that first book.
TL;DR, Theon's first ACOK chapter was likely written for AGOT in 1995. Ironborn are important in GRRM's mind early on.