In the mid-1600s "Queen dick" was a silly, imaginary, impossible character; Dick is a boy's name, and queens are girls. End of.
Queen Dick appeared in a number of variations; a "story of Queen Dick" was a fairy tale, or, perhaps, a lie. 'In the reign of queen dick', likewise, meant 'never'.
This appears to be a long-standing and well known idiom, but amusingly, it only came to be used in print in 1663, when it became useful as a punning comment of the politics of the day: when Oliver Cromwell died, his son Richard Cromwell briefly stepped into the role of Lord Protector of England in 1658. He was not well fit for the post, and lasted only eight months, never carrying the title of king, and was much mocked by political writers of the time.
"...and now styled the most Noble Lord Richard, and rife discourses there were of Richard the Fourth, but they proved no more than the story of Queen Dick."
-- Flagellum: or, the Life and death, birth and burial of Oliver Cromwell, By S. T. Gent. i.e. James Heath, 1663.
For a brief period Queen Dick became a cunning reference to Richard Cromwell, and then it faded back into obscurity -- or, more likely, back into common usage, but not written usage, as it continued to pop up from time to time well into the 1800s.