"Sam Hall", a novelette by Poul Anderson, first published in Astounding Science Fiction, August 1953, available at the Internet Archive.
I read this in the mid 70's. It may not have been a new story at that time.
Any of these covers look familiar? If you read it in the 1976 collection The Best of Poul Anderson then some details in the excerpts below may not exactly match what you remember because, according to the ISFDB:
Note that the story has been revised for The Best of Poul Anderson probably by Anderson himself. The salesman in the opening paragraphs no longer has a "punched card" which is checked for "holes," but simply a "card" that's checked for "magnetic encodings." He's no longer bound for "New Pittsburgh," but for "Cincinnati." Superfluous words have been removed from many sentences, etc.
In a future society run by a military dictatorship, the protagonist works as a lowly clerk in the giant complex the government uses to keep track of everyone.
Thornberg limped over to his desk, sat down, and took out a pack of cigarettes. He held one for a moment in nicotine-yellowed fingers before lighting it, and there was an emptiness in his eyes. Then he puffed ferociously and turned to his mail. As chief technician of Central Records, he received a generous tobacco ration and used all of it.
The office was not large—a windowless cubicle, furnished with gaunt orderliness, its only decoration a picture of his son and one of his late wife. Thornberg seemed too big for it. He was tall and lean, with thin, straight features and neatly brushed graying hair. He wore a plain version of the Security uniform, with his insignia of Technical Division and major's rank but no other decoration, none of the ribbons to which he was entitled. The priesthood of Matilda the Machine were a pretty informal lot for these days.
He invents a revolutionary figure out of whole cloth by creating a file for him (I'm not sure but the nonexistent rebel leader may have had the first name "Sam")
He names the imaginary rebel Sam Hall, after the hero of the English folk song:
By God, he thought, I'll give them Sam Hall!
His fingers began to race; he lost his nausea in the intricate technical problem. Slipping a fake spool into Matilda—it wasn't easy. You couldn't duplicate numbers, and every citizen had a lot of them. You had to account for every day of his life.
Well, some of that could be simplified. The machine had only existed for twenty-five years; before then the files had been kept on paper in a dozen different offices. Let's make Sam Hall a resident of New York, his dossier there lost in the bombing thirty years ago. such of his papers as were on file in New Washington had also been lost, in the Chinese attack. That meant he simply reported as much detail as he could remember, which needn't be a lot.
Let's see. "Sam Hall" was an English song, so Sam Hall should be British himself. Came over with his parents, oh, thirty-eight years ago, when he was only three, and naturalized with them; that was before the total ban on immigration. Grew up on New York's lower East Side, a tough kid, a slum kid. School records lost in the bombing, but he claimed to have gone through the tenth grade. No living relatives. No family. No definite occupation, just a series of unskilled jobs. Loyalty rating BBA-O, which meant that purely routine questions showed him to have no political opinions at all that mattered.
Too colorless. Give him some violence in his background. Thornberg punched for information on New York police stations and civilian-police officers destroyed in the last raids. He used them as the source of records that Sam Hall had been continually in trouble—drunkenness, disorderly conduct, brawls, a suspicion of holdups and burglary, but not strong enough to warrant calling in Security's hypno-technicians fo quizzing him.
and gets the government to waste resources chasing him down. Naturally, since he doesn't really exist, he can never be caught.
"Sam Hall is a shadow," said the cop. "the most careful checkups eliminate any chance of his being identical with anyone else of that name. In fact, we've learned that the name occurs in a violent old drinking song—is it coincidence, or did the song suggest crime to Sam Hall, or did he by some incredible process get that alias into his record instead of his real name? Whatever the answer there, we know that he's ostensibly without military training, yet he's pulled off some beautiful pieces of precision attack. His IQ is only 110, but he evades all our traps. He has no politics, yet he turns on Security without warning. We have not been able to find one person who remembers him—not one, and believe me, we have been thorough. Oh, there are a few subconscious memories which might be of him, but probably aren't—and so aggressive a personality should be remembered consciously. No undergrounder or foreign agent we've caught had any knowledge of him, which defies probability. The whole business seems impossible."
After a while the protagonist gets the idea to start planting evidence of secret association(s) with the fake rebel leader in the files of prominent figures in the government - who then turn on each other, eventually bringing the government down.
"You traitor!"
"And a very effective one, wasn't I? I've got the government turned end for end and upside down. The Army's in an uproar, officers deserting right and left for fear they'll be arrested next. Administration is hogtied and trembling. Security is chasing its own tail around half a continent. Assassinations and betrayal are daily occurrences. Men go over to the rebels in droves. The Army of Liberation is sweeping a demoralized and ineffectual resistance before it everywhere. I predict that New Washington will capitulate within a week."
"And your doing!" Finger tense on the trigger.
"Oh, no. No single man can change history. But I was a rather important factor, yes. Or let's say—Sam Hall was."
