My last week's pay at my former employer was paid out twice. They want their money back, which I will gladly do, but here is the problem: Part of the gross pay went to my 401K (no company match involved), part to the IRS, SS and medicare taxes and my net pay. Can I withdraw the 401K money from my account? Also, how do I recover the taxes portion -as an amended tax for that year or as credit in the next year?
Typically, your employer is able to 'undo' all those activities retroactively - so you would end up as if the issue never happened.
They will have to fill some forms for most pieces, and it will be a pain for them, but as it seems to be their fault, they can't really complain. I would expect them to maybe forget about the Social Security part, as it is a nightmare to change retroactively, but again, it is their problem, not yours.
You should agree to get a corrected paycheck (= corrected down to zero), and pay back your net payment from the wrong one, and also agree that they take the overpaid money out of your 401k - that is all fair. They cannot request you to pay them back the full gross amount - you never received that.
Did you roll over your 401(k) to a new provider, or is it still at the employer's benefits provider? With respect to the 401(k), if it's still in their account it's not yet titled to you and the company should have control via their service provider. Did they ask you to withdraw funds from the account for this event?
Did they pay you in paper checks or with direct deposit?
Unless this former employer is bad at HR (and since they issued two pays upon separation: it's in the realm of possibility that they simply are very bad at HR), they probably put boilerplate authorization to correct direct deposit payroll errors into the contract documents you signed. This has been a feature of every direct deposit employer contract I have worked at. I would acknowledge their courtesy note that they are doing the correction (they probably are making a good faith effort to keep you from getting an unexpected overdraft) and only take any direct steps they ask you to do.
Once corrected, it's their responsibility to send you your correct end of year W2 with total gross and withholding amounts. Given your experience to date, I'd probably write myself a note with what I'd expect to see, and validate it when they send it.