>I know that I'll have to order a new queen and requeen this hive, but with all the talk of recent difficulties with re-queening I'd like to give her the best shot.
She doesn't have much of a shot at all.
>I understand that to get rid of the laying worker, I'll have to shake out the hive >100yds away.
It doesn't matter. The laying workers always come back anyway. All the latest research has proved this and all my experience would concur. All it does, if you leave the old equipment there, is demoralize them enough to improve (but certainly not guarentee) your chances of them accepting a queen.
>How long before I re-queen should this be done?
I don't think it matters. They are already queenless. I'd say sooner is better than later, but I would put the odds that it will fail regardless.
The only sucess I've really had is to either give them some brood once a week for a couple of weeks and then introduce a new queen (and don't bother to shake them out) or put a queenright nuc over a double screen so they can smell the open brood and get used to the smell of the queen. After a couple of weeks do a newspaper combine.
But my REAL advice is move all the equipement and shake out all the bees and give the combs to your other hives and call it a loss. The bees will find their way into other hives and your problem will be solved without wasting several queens and a lot of your work.