The gholam are so completely alien, I doubt they are even as much human descended as the Trollocs & Myrdraal. Furthermore, while Gray Men are often lumped in with Shadowspawn, they aren't, they are altered humans, not constructs. I could easily believe that Aginor & co had nothing to do with their making and that they were simply a phenomenon that occurred through the Dark One's actions. They're humans who give up their souls. That's it. In fact, that doesn't seem like something a channeler could even do. Note the lack of channelers present when Moghedian is fitted with her mindtrap. I don't think there is anything that people can do, with the Power or not, to affect a soul. Even balefire has no effect on souls, contrary to a lot of ignorant readings of Rand's demonstration in tGS. A soul is metaphysical in a way that even the One Power and Tel'Aran'Rhiod are not. Even the Dark One can't destroy it or mess with it, aside from influencing its movement to and from the world of life. Maybe he can mess with those who have chosen to place themselves in his power to degree, even if only by indulging in Shadow-congruent behavior, but that's about it, unless maybe if he ever wins his final victory.

So I think the Dark One could remove someone's soul, but not a Forsaken.
Although soul removal does not make sense because then they'd die - rather I believe it is somehow suppressed or muted, as a cause or side effect of the process that renders them beneath the notice of most. Or else maybe a Grey Man IS undead, with maybe some motive power of the Shadow keeping the corpse warm and animate.

I think the Gray Men might have actually predated the Shadowspawn. At the very beginning the Dark One might have sought ways to access the physical world, presumably limited even with the open Bore and one way to do that might have been to trick people into vacating their bodies to serve as his avatars. I think it's possible that he always wanted a way in or working through the Gray Men whetted his appetite for an avatar and began with ordinary Myrdraal, who would be more compatible with his nature and power and eventually Shaidar Haran.

Even with that custom-made form, however, the Dark One had limits. It makes sense to me that if Grey Men are actually undead and powered by him, his actions are filtered through their perceptions and remnants of their minds and his own influence is limited. He is so antithetical to nature and life that is possible a human brain, influenced by a lifetime of a human soul using it, is not set up to run his software, so the Gray Man, while under the influence of the Shadow and thus susceptible to the commands of a Forsaken, can't manifest the actual will of the Dark One.

As far as their supposed purpose as assassins, that's simply the outcome of the properties of the Gray Mens' transformation. If they are so utterly unnoticeable, infiltration is the obvious mission. Another possibility is that assassination is only one of their functions, but it's the only one people are aware of, because they never ever find out if a Gray Man is simply doing recon. It's only when a person dies or is attacked that anyone even becomes alerted to their presence, so if they are just spying, or leaving secret messages for Darkfriend cells, they never do get caught. As for why they have that property, well, it could be there is some sort of resonance between souls that causes people to notice other people or distinguish them in their minds between unliving things. It certainly explains how Verin was able to identify the lack in an Ogier while in a stedding (or how Ogier could tell, for that matter). But even if it is a characteristic imparted by their transformation into Gray Men, it makes sense that this would be done to the very first extreme servants of the Shadow. The Aes Sedai who went over would get the black wires and the elite among them, access to the True Power, while the first or most dedicated Darkfriends, who don't need souls if they can't wield the Power, lose 'em and get their own change, which, in the very earliest days, before AoL society fell apart enough for the Dark One to begin gaining a foothold in the world, and his armies to form and begin conquering for the Shadow, would be most useful passing under the radar. Rather than a monstrous transformation to make them beasts and brutes, which would automatically horrify people, the first people changed to serve the Shadow would be stealthy and avoid attention so as to help the Dark One's servants lay the groundwork for his emergence. The Trollocs came later, when war broke out and they needed shocklance fodder. Also, when people are first beginning to figure out how to fight, when there are no real martial arts or warcraft circulating, being able to walk right up and strike before anyone knows you are there is an even more decisive advantage. Darkfriends were figuring out military stuff at the same time as the normal people, even if they would have been doing it first, and the good guys only in reaction. Ironically, there were probably some good guys who never served the Shadow or were even tempted, but who probably still found themselves investigating the lethal potential of the sword game, by the base impulses inspired by the Dark One's touch on the world. So there would probably have been less technical advantages to the Shadow's side at the outset than might be assumed. If you were to rank the Forsaken by demonstrated or proven martial skills, the top three, Sammael, Bel'al and Demandred, were all leaders of the Light side in the beginning. I'd even go so far as to say that the initial high-ranking or elite followers of the Dark One would have had disproportionate numbers of physical cowards. So ultimate stealth, rather than raw power or physical lethality would have been much more useful. And AoL tech would make physical forms of invisibility (ie fan cloth)less practicable, because of different kinds of sensors or imaging devices. But having the ability to see something is useless if your mind won't pay attention to it.

So, in short, I think Gray Man were among the first innovations of the Shadow among those we know about in the current time of the story.