My story revolves around 8 angels that my players must defeat. The thing is I want them to look for them in no particular order. How can I balance an enemy easily in advance, since they may encounter them at any given level, depending on which one they find first?
Strictly speaking, you can't balance them at all in advance, since the players could not only fight them in any order, but could conceivably fight any number of other things in any order, meaning they could be any level at all when they reach any given angel.
You should build a template for each angel with each of its powers in advance, and possibly mark off some powers as "high level" powers that the angel will only have in certain level ranges. Leave out all the numbers, such as to-hit and damage. Then, when the players reach that angel (you should at least have some forewarning about which angel they'll reach in a given session) fill in the numbers to fit the party's stats.
Soulrift has a great answer, but you have some other options.
One option is: don't balance at all. In some sense this gives the most sense of realism. If they go after an angel they aren't ready for yet, they will likely be defeated, but if they are smart they will run before they take too many death's or permenant losses (a bit of Deus Ex Machina can help make sure they get away.)
If they go after one that is too powerful for them, they know they have to do something: increase their own power level, better prepare in a way that is tailored to that specific adversary, or bring along help (allies or NPC hirelings.) That makes it feel real, makes it feel like their adversaries are powerful beings in an organic universe rather than a game piece tailored to challenge them just a bit.
On the other hand, if they go after one that is too easy, they will get an easy win, but done right that can also make them feel awesome. "We not only beat up this powerful being, we did so without breaking a sweat. Our enemies should now quake and lesser heroes stare in admiration" As long as they think it was easy because they upgraded their characters, prepared for the fight, and used the right strategies rather than easy because you nerfed the adversary on purpose then this can be extremely satisfying.
It is even more satisfying if they get beaten, go off and fight other angels and gain a few levels, and then have an easy fight against the one that beat them before.
Then there is the other extreme: Adjust during the fight.
This of course is pure Deus Ex Machina and might even feel like "cheating". But it involves the least work for you and lets you gauruntee that the fight will be challenging but winnable.
The players don't get to see the enemies character sheet. If the fight starts to look too easy, you can tack on some powers and add HP. You can't adjust things like damage or to-hit numbers because the players probably already have a sense of that, but you can adjust HP, spells, power, and (to a degree) equipment freely on the fly.
It would probably seem a bit cheesy, but you can even use the video game trope of having the angel suddenly shift to a more powerful "final form" if they get a complete win too early or its much too easy. This is slightly less cheesy if you foreshadow the shapeshifting in some way before they encounter the adversary.
On the other hand, if the players are losing, you can cross off some of the powers you originally expected them to have and knock off a bunch of HP
I'd suggest pregenerating each angel at the first level the players might encounter it at, and then add some levels and unique traits over time. As the players level up, so do the angels.
This shouldn't take more than half an hour between sessions every time the PCs level up, and depending on how you set them up (whether they have classes ect.) it could take as little as 5 mins.
Some great answers here, especially on ways to handle the mechanics and the work load. As several posters have mentioned, from a plot/in-world mechanics perspective you don't want to give the players the feeling that the universe is tailoring itself to them. One thought: given that the angels are all related in some way, you could start with all of the angels at a lower level, then have the "essence" of a fallen angel transfer to the remaining ones. Surviving angels might have a boost to HP or strength, or be able to access the fallen angels spells/abilities. This would compound and concentrate as more and more were defeated, and if their powers vary, the combinations could make the later encounters quite formidable. Depending on the effects they witness and the clues you provide, clever players might even look for ways to interrupt those connections to weaken their foes...
This is really a question of personal preference. Generally speaking, I let my players know ahead of time that my world is a big place and it's enhabitants are there regardless of the players level. That means if they decide to go spelunking at lvl 1 and end up in the middle of a Naga's/Hydra's lair/nest/whatever, well that was it's cave and the fact that they intruded on it's liar is something they'll have to deal with.
That said, I like your idea of giving the players a real choice and obviously don't want them to suffer because they arbitrarily went after Angel 7 instead of Angel 2. The way I would handle this takes a lot more work, but I'm kind of a perfectionist so thats just the price I pay. I would make all of the Angels at each of the levels they might encounter them. Yes, I know 8 Angels * X Number of possible Enouter Levels is a lot of work. But Thats just the main way I would handle it.
2 other good options include:
Cohorts..there's nothing wrong with the Angel's having Cohorts. They can be rolled up well before the adventure and since they're not directly assigned to an Angel then you can have different cohorts for different ECLs. While this takes a little more work its not as much as my first option and the Number & Strength of Cohorts an Angel has can be decided right before the encounter..The PCs don't know the difference..which leads me to my last option.
Unless your clues include specific details/names/etc there is no way the players know the difference between Angel 2 or Angel 5..just like they don't know the difference between taking the left path or right path at the fork in road. So while it doesn't jive 100% with your intent, if time is an issue you could always just switch the names/numbers of the Angels they encounter. TBH I like this option least, but in a pinch it might have to do if time was an issue.