When and where was the phrase olden days coined?
According to Google's Books Ngram Viewer, the phrase was coined some time around 1800 and peaked around 1930:
The oldest reference I could find for "olden days" is the 1805 Tobias: a poem : in three parts by Rev. Luke Booker:
And the oldest I found for "olden times" is Poems on Affairs of State from 1620 to this Present Year 1707, in a poem called "GIGANTOMAXIA, or a full and true Relation of the Great and Bloody Fight between three Pagan Knights and a Christian Giant" by an unknown author and originally published in 1682:
I suspect these stem from the Romantic era:
Take for example this 1868 poem called The Olden Days.
The phrase is a good deal older than the other answer suggests. It’s already found (as olden dawes) in Cursor Mundi, specifically, in the ms. Trinity College R.3.8: 'Now com my sawes Þat I seide bi olden dawes'. This entry in the Middle English Dictionary dates that citation to ante 1400 and offers another from ~1426. Before that we find it in Old English 'in olden days', e.g., in the Life of St Æðeldryþ in Ælfric of Eynsham’s Lives of Saints (late 10th century), in Ælfric’s Homilies, and in the charter S 1146 from 1062x66.