Clone stormtroopers have indeed been around as an idea since the OT, but the original idea was that the clones had been the villains of the Clone War, the guys whom the Jedi fought against. Lucas even told Leigh Brackett this was what happened (and that the clones started a war against the Republic), in the ESB story conference.

Mind you, the Clone Wars at that point were very hazily imagined--they merely provided an interesting soundbite of backstory, and also possibly explained the GFFA's preference for robotics over cloned replacement limbs etc.

In other words, the Clone Wars were very much like the long-ago Butlerian Jihad which is part of the backstory in Dune (the source of so many SW ideas). That was a war in which evil robots attempted to enslave humanity, and after which the victory of humans led to a religious prescription outlawing robots and "thinking machines," i.e. computers (but not clones--an inversion of the SW situation).