I'm no expert on bee-breeding, and I found myself facing some of the same questions as you. Here are some pointers based on my own muddling about.
The short answer to your question is, yes. If you need a new branch, you have to start with a princess, but of course, you can start with whatever species you have. You don't necessarily have to go back to "the beginning", if you have appropriate middle-of-the-line bees.
As for extra bees machines, the Isolator actually allows you to extract the species of a bee, as a serum. You can then inject that species serum onto any other bee. (Disclaimer: I only tried this once and it was on a drone, not a princess, but it worked just fine). Note that the extra bees machines are pretty expensive in terms of materials and mainly... power. Boy do they need power. So just be ready for that. You'll also need a good supply of drones to toss into the genepool to provide liquid DNA, if you choose this route.
If you want to go with old-fashioned breeding, then yeah, get some more princesses/queens by raiding more hives and so on.
One other possibility is, and this is more of a question than an answer... in theory, if you have two bee species that don't produce a "known" mutation, and you interbreed them, is there just a random chance (over time) that the offspring will be one or the other?
For example, if I have a forest princess and a bunch of noble drones, those two don't produce any combination normally, so if I just keep breeding them together, is there a chance that over time, I'll eventually end up with a noble princess? Something I might test out myself...