Nigel Rees, A Word in Your Shell-like: 6,000 Curious & Everyday Phrases Explained (2004) offers this discussion of the phrase:
(as) queer as a clockwork orange The title of the novel A Clockwork Orange (1962; film UK 1971) came, according to its author Anthony Burgess, from a Cockney expression. 'queer as a clockwork orange' (i.e. homosexual). This had been in use since the mid-1950s, Paul Beale states in Partridge/Slang, though few others had heard of it. Perhaps Burgess simply got the location wrong as the phrase was reported from Liverpool in Shaw & Spiegl, Lern Yerself Scouse (1966): 'E's as queer as clockwerk oringe' — 'He enjoys being hugged after scoring a goal' (this was a year or two after Burgess's novel was published, of course). Another attempt at explaining the title has been that Burgess worked for many years in Malaysia, where the word 'orang' means 'human'. As to the title's relevance to the story—which has no overtly homosexual element—this is debatable, unless 'queer' is taken just as 'odd' and without the sexual meaning. The following passage from the novel hints at a possible reason for the choice of title: 'Who ever heard of a clockwork orange? ... The attempt to impose upon man, a creature of growth and capable of sweetness, to ooze juicily at the last round the bearded lips of God, to attempt to impose, I say, laws and conditions appropriate to a mechanical creation, against this I raise my sword-pen.' The book describes an attempt to punish its criminal hero, Alex, by turning him into a 'mechanical man' through forms of therapy and brainwashing.
A version of Lern Yerself Scouse appears (without attribution) on a Geocities page, where the entry for "E's as queer as clockwerk oringe" appears under the subheading "At the Football Match."
The Paul Beale reference is to Eric Partridge & Paul Beale, A Dictionary of Slang and Unconventional English, eighth edition (1984), which has this entry:
queer as a clockwork orange (, as). 'Homosexually weird (precedes film of the same name): Royal Navy: 1960s' (Peppitt). The film title is A Clockwork Orange, based upon Anthony Burgess's notable novel, also so titled—a strange an moving book, published in 1962 {P.B. the phrase has been in low gen. and Services' use since the mid-1950s.} In a letter, 1971, A.B. told me, 'I first heard the expression ... in an East End [of London] pub, and there was a time when the BBC used to put on Cockney plays that made use of that juicy trope.'
The Peppitt mentioned in this entry is Lieutenant Commander Frank L. Peppitt of the Royal Navy Reserve. His information seems to be based on recollection rather than on contemporaneously recorded examples.
Jonathon Green, Chambers Slang Dictionary (2008) has this brief entry:
queer as... ...a clockwork orange 1 {1950s+} extremely odd. 2 {1970s} ostentatiously homosexual
This entry is interesting in several ways, starting with its assertion that the expression dates to the "1950s+" despite Green's assertion elsewhere (see JOSH's answer) that "the first recorded citation [of the complete phrase] comes as late as 1977." It is also intriguing that the original meaning Green ascribes to the phrase is simply "extremely odd." And third, it asserts that the "homosexual" sense of the phrase arose in the 1970s, whereas Rees states that Lern Yerself Scouse cited that sense of the phrase in 1966.