I don't think shaking out the bees works very well, since the laying workers will generally find their way back to the hive too. Doing a combine followed by a split is more of a production than dropping in a frame of eggs, but it it probably faster. If you have lots of open brood available to donate, I'd try that. If not, do the combine. If you decide to add brood, make sure you don't move the queen from the donor hive by accident.
Putting a new queen into a laying worker hive is likely to result in the queen being killed since there is no open brood and the hive thinks they already have a queen.