There is a sure-fire, relatively easy way to requeen; can you bear to hear someone talk this way? It uses a "Thurber Long Cage" as described in Roy Thurber's book, "Bee Chats, Tips and Gadgets", now out of print. It describes a cage into which a new queen is placed which provides both a way for the queen to be fed and her pheromones picked up and for her to escape any bees which try to harass her.
A cage is bent up from 1/8" hardware cloth which is 3/16 thick, an inch or so wide and most any convenient length. Wood plugs are whittled to close each end. A "sheet metal tool" vicegrip makes the bending easy. Locate the mating edges in the middle of one side, not at corner. Don't overlap the mating edges, let them be 1/8" apart. Solder or epoxy the corners together.
First remove the old queen and wait a couple of days to be sure her pheromones have completely dissipated. If you are buying a new queen, the safest way is to find the old queen, put her into the cage and return her to the hive. Then call and order the new queen so you will know one is available and about when to expect her. Then it is easy to remove the old queen because you know right where to find her, right? When the new queen arrives, go into a room which can be closed off and which has a window to which the queen will fly if she gets away from you. Open the shipping cage and tease the attendant bees out, flipping them up into the air to get them out of the way. I presume it is worthwhile not to cause them to release any alarm phermonone. Catch the queen with a queen catcher (from any bee supplier). I urge that she be marked with a queen marking kit at this time. Then induce her, using patience, to crawl into the cage. Place the cage in the hive between two drawn (not foundation) frames in the middle and close the hive. (You can see you will need to have contrived some way to keep the cage from falling down. I cut the hardware cloth to leave one wide side extending and inch so it can be bent 90 degrees to the outside to form a handle.) A couple of days later, to provide a large factor of safety, open the hive and withdraw the cage. Be careful not to pull the bottom plug out of the cage! Now you have to be careful to avoid a problem. If you open one end and permit any bees to go in with the queen, Lord only knows how long it will be before she decides to come out! So contrive to release her onto the top bars when she comes to the open end - she is likely not to notice it since all she sees is open space everywhere - and watch her dive down into what is now her hive.
Focus on what has happened. The old queen's phermones are gone. The bees are mostly anxious to have a new one. They have been feeding the new queen through the cage and picking up her pheromones for a couple of days and distributing them through the hive. All the bees are now comfortable with her presence and her finally being free is nothing new. I have never failed to have a succeessful introduction. (Provided only that there is not a virgin queen in the hive unbeknownst to you!)