My guess is that some of the first shamans were guys with a gimpy leg (or a lazy streak) who couldn't (or didn't want to) go out hunting. They said, "Hey, you know what? You guys go out hunting and I'll stay here in the nice warm cave. No, wait, hear me out. I'll stay here in the nice warm cave and I'll talk to the gods for you. I'll ask them to send some nice juicy mammoths in your direction. They're bound to feel sorry for me on account of my bad leg (bad back) and all."
The belief in spirits and/or an afterlife may have been genuine but the idea of intercession strikes me as a con from day one.
I think you're projecting too much 21st century mentalities and ideas onto other people, without looking at the actual practice of shamanism.
Not all shamans are allowed to sit on their arses in camp while the other men go off hunting. In some modern shamanistic societies, the shaman has to take part in hunting and gathering the same as everybody else. This is particularly true in resource poor areas like the Canadian arctic, for obvious reasons. You can make an argument that they get increased status and maybe some extra resources, but the idea that they can just sit and leech off everybody is certainly not universal, and I don't think we can assume it's the origin.
Secondly, shamanism isn't always that easy. The rituals involved in initiation, and in attaining a trance state, often involve self-mutilation, enforced isolation and starvation. Starving yourself into a delirious state until you start hallucinating 'the spirit world' does not seem like the easiest way of tricking yourself to a share of the hunt.
Not all shamans are, or were, men. Some of the earliest archaeological evidence of shamans in Europe and the Middle East suggests they were more likely to be women, so skipping out of the hunt doesn't seem relevant. You could argue they were avoiding other work, I suppose, but I don't really see it as a fair assumption.
A settled priesthood who get paid from other people's work without seeming to do very much seems to have evolved out of people who had to work, and who did often unpleasant things to themselves to intercede with the spirit world. It seems much more likely to me that they genuinely believed in what they were doing than that it was all an elaborate con of dubious benefit to themselves. Perhaps, once settled societies started producing enough surplus to support a priestly class, we can start talking about cons, but even there it doesn't seem necessary. The priesthood can still be seen as a natural progression to a parasitic class, without anyone ever planning it this way.
™ Version 4.2
