Keeping this on top for users having similar problems: I somehow managed to eliminate the stutter by doing the following:
* update the Xbox 360 wireless receiver driver to newest version: go to Device Manager, look for Xbox 360 Wireless Receiver under "Microsoft Common Controller for Windows Class", right click and choose "Update Driver Software", "Browse my computer...", "Let me pick from a list...", "choose driver version 2.1 from 2009
* keep the controller turned ON at all times while in game, even if you don't use it
* disable AntiAliasing in the Postprocessing video options.

---

I just purchased the game today and, unfortunately, the game skips frames every second. It is literally unplayable. I tried every thing imaginable: clean uninstall of drivers and install latest version or latest stable, fiddle with graphics (game skips regardless of settings, no matter if on low or ultra, vsync on or off, etc.), disable GOG Galaxy overlay, uninstall Galaxy completely, etc. At this point, I can only conclude I regret the money spent on this game.
I have *zero* problems with any other games; I play the likes of Doom, Dragon Age Inquisition, Metro Last Light, Rise of the Tomb Raider etc. on Ultra settings with minimum 40 fps and 60+ fps on average. Yet this game is unplayable regardless what settings I choose.

System: i5 2550k @ 4.3 GHz, Radeon RX480, 8GB RAM.

Please tell me there's a solution for this! Give me a reason not to hate myself for wasting time and money on this game.

Here's a recording of the problem: -deleted- nevermind apparently GOG doesn't let me post messages if I have links in them. It doesn't even show a message or anything, it just does nothing when I press the Post my message button. Tried three different browsers, had to google the problem to figure it out. I'm starting to see a pattern here. Youtube video code is y3Sy5JQRwI4 if anyone is interested in seeing the recording.

have you tried reinstalling or verifying/repairing the game through galaxy?

Yes, I tried repairing the game, it took an hour and it solved nothing.

After more than 4 hours of trying different configurations, fiddling with my peripherals and searching the web for a solution, I managed to get closer to the cause: the problem seems to be triggered by the XBox 360 controller I have attached to my desktop through a Microsoft Wireless Adapter. When the controller is turned off, the game stutters like in the video. As soon as I turn it on, even if I don't use it, the stutter stops. It is the most stupid behaviour and it makes no sense, as the controller automatically closes off if not in use, so I would have to keep turning it on. It's just beyond stupid, it can't be even turned off in the game options. I have this setup since 2011 and I never had this kind of issues with any other game!

The problem for me now is that, in the process of trying to get this game to work I kept switching the wireless adapter on different USB ports and managed to fry it. It is now dead, the light no longer lights up on the adapter when I plug it in, and it's no longer detected by the system (it's a common problem with these adapters, a fuse on the integrated board can be fried). So now I'm not even able to use this workaround, and since the game doesn't have an option to choose between a controller and keyboard + mouse control scheme, like any other game in existence, I'm stuck in this absurd situation.

Btw, even when the controller was working, the game still had the same problem when I was turning AntiAliasing on. I could max everything, including Nvidia hair and all post-processing (except AA), and get perfect performance, but as soon as I enable AA in postprocessing section the game craps itself (same stuttering issue as in my initial post). This reeks of bad QA and lack of user friendliness (see the inability to disable controller in game options).

This game is just a bag of disappointment for me, I doubt I would enjoy it even if I could get it to work at this point. Nothing left but to throw it in a corner and accept I threw away my money.

I have to say that it sounds like a system specific issue to me, not a game issue -- I don't care if other games work, that's irrelevant. The mere fact that you say you can run the game with Hairworks maxed but not with AA in any form supports this -- Hairworks is the absolute framerate killer in Witcher 3, not AA. My first avenue, in your shoes, would be to check/adjust any game profile for Witcher 3 in your video card control panel.

No worry mate, not your fault. Thanks for taking the time to answer! Well, there are lots of users complaining about the same issue, and they also found out that disabling AA solves the issue.

Game profile is default, I didn't fiddle with the video card settings in any way. I attached a picture with the settings.

Here's a recording with the issue in question: https://youtu.be/Elbiz9zuzbg. Game seems to have been stabilized now, but as soon as I disconnect the controller or enable AA the stutter is back. At least I can play it now, as long as I disable AA and play it with a controller.

For anyone having similar issues, I added some steps in the first comment that might help fix it.