During the late 60's and throughout the Cold War, the Soviet Union ran several very succesful spy programs. One of their strengths was pitching these groups against one another, and thus capturing information regarding a Western secret from several different sources, thus getting a very complete understanding of what's going on in the West.
Author Victor Suvorov, in his book Aquarium, describes being recruited from the military into the Spetsnaz, and being groomed to eventually join the elite Soviet Military Intelligence Directorate, or GRU for short. He describes the training, tools, and support that their agents received, as well as the many security measures which were employed to determine that information was valid, and that agents remained loyal. It's a incredible read, and I highly, highly recommend it. That being said, I'll go over the main points:
The people being recruited into the GRU were all military personnel. Suvorov himself was a tank commander when he was first noticed by the officer who eventually had him transferred out of the tank corps, and into Spetsnaz. What set him apart from others was an ability to think independently, which marked him as a useful underling. (a tank broke down, blocking the exit from the military base, and the entire battalion was stuck in the middle of a military exercise. Without waiting for orders from higher - the Soviet mentality - Suvorov ordered his plattoon to turn off the main road and drive straight through the base perimeter - walls, barbed wire and all)
Once in the Spetsnaz he was then trained as an elite special forces soldier, as well as in extreme survival techniques behind enemy lines, and disrupting both government, law enforcement, and military agencies. Things like sabotage, typical police and military deployments, etc. avoiding, and even fighting trained police dogs, surviving off of the land in extreme situations, etc.
I'm detailing all this because I want to underline that this guy had elite military training before he became a spy. He proved that he was a tough bastard, and that he had no issues killing people before he was even approached by the GRU.
He was then subtlety tested by the GRU without it even coming to the knowledge of his own officers. He was instructed to play sick, and get a medical discharge for a few days (difficult to do in and of itself). He was then to slip out of the base undetected, undergo a night mission across the border, and return to the base undetected. He succeeded, not knowing why, or questioning orders, and was then approached by a GRU officer with a recruitment offer. As you can see, even for an elite soldier, he was still supposed to accomplish feats which not just anyone would get away with.
Once in the GRU (officially he was part of a scout division or some such thing, and still part of a regular military unit) his training began. The recruits were taught by former spies who had, essentially, screwed up, and were known to Western spy and law enforcement agencies - aka useless in the field. They underwent psychological torture and extreme testing. They would be held in a room, in front of a panel of "interviewers" for hours, and hours and asked question, machine gun style. His answers were all recorded, the point being to be as accurate as possible under extreme stress. Sometimes they would be kind to him, other times he would be lead on with some false information, or treated very poorly. He was expected to see through the subterfuge, ignore the false leads, and still provide an intelligent answer to what he was being asked.
Another huge part of his training was recognizing people, and places at a glance. He would have to memorize hundreds of faces, then recognize the same people with different haircuts, clothes, wearing glasses, etc. There was a major, major focus on this to the point where the agents developed almost photographic memory for any sort of detail that you and I might forget 10 seconds after meeting someone.
Memorizing languages was also a must, even if he could barely pronounce the words. The focus was always on memorization.
His final exam was to perform spy duties in Moscow, as if an enemy agent. The KGB cadet's final exam was to catch them, so there existed very real competition even to graduate. He was expected to completely memorize the city in which he operated, to know every nook and cranny, every street, where every door lead. Every hiding spot, every possible location for a dead-drop, and even which stores are located where. He succeeded in his mission, and was assigned abroad, as a diplomat to a Russian embasy.
Once there his training only continued. He was expected to memorize the city where he would be operating, to understand everything about their law enforcement procedures, deployments, etc. His training now started focusing on human interactions. Reading people at a glance, dominating them by sheer strength of will, through nothing more than a hand shake, or looking them in the eye (he describes training by going to the Zoo and staring tigers in the eye).
His loyalty, skills, and knowledge were always being tested. Finding a letter addressed to someone else in your mailbox was something to be immediately reported to your superior officer - failing to do so could be signing your own death warrant.
As he rose through the ranks of the GRU you can see that the focus turns from any military skill to pure endurance, grit, and psychological manipulation. Shooting people, blowing stuff up, etc. is reserved for James Bond novels. Getting to know just the right people, and convincing them to grant you favors was their bread and butter. Subtlely putting them into a situation where they can't refuse your requests, etc.
For more details get the book, it's really a great read.