Again, chaos soldiers are cool but impractical, at least for now.
But this post is mainly for a deliciously evil idea: Make a seasonal change activate a sleeper disease. Start off with a non-supernatural bacteria or virus that does little to harm its host under deactivated conditions. If it obeys our commands directly Valahun will immediately notice it. It has to do some harm to the host in order to reproduce and spread itself, so it might be best to make it look like a Vehna flu. Should be spread through air and by surfaces, and maybe by sneezes. It should be biologically set to act differently in the presence of its activator. Possible activators include pollen and certain temperature ranges. If it is winter, we can set this to activate during spring or summer, allowing plenty of time for an invisible disease to spread to everyone. Even a little bit of it retained in your body should be enough to kill you when the activator is... activated. Except I say we don't make it kill them. Instead it should make them insane and attack a section of the brain that normally makes them want to worship Valahun. The morals section, maybe? Of course, that has it's own terrible, terrible issues. Though it will cause a good amount of confusion and panic. At this point we can allow our disease-immune followers to spread our worship via insanity-repressing idols that only affect people who choose to worship us. The rest will die. Preservation of the instinct of self-preservation should get us followers. As for Organis himself, well he should be long gone, hiding in a really far away place. Even magical doohickeys of forced teleportation should have distance limits. Should also be sneaky while running away, and do it before activation. Maybe, instead of breaking Valahun's doohickeys, we can transplant them onto a lifeless Organis mimic? We should put our god-smell on it too, and suppress our own god-smell, so Valahun'll go after the mimic while we escape. Perhaps mimic should be made to constantly laugh, so as to mock/psychologically destroy Valahun while also making him slower to realize the mad puppet is just a puppet. Escape location should be somewhere none of the pantheon gods own. We could go into space, but there's too much open space there, and we'd be easily spotted. We could go deep into the Shadow's land, and maybe even bluff Valahun into thinking we've sided with the Shadow. Now the biggest issue is creating and inserting the disease into the population without Valahun knowing it. If he even observes us manipulate a microscopic bacteria for a second, he'll immediately become suspicious and examine bacteria until he finds something he's not familiar with. Then he'll analyze it and figure out what it does. Then he'll kill us and make an antidote. Hence it might be best to make a pet bacteria farm, where we can make all sorts of silly and different colored bacteria and viruses and watch them fight and grow. There should be thousands of different kinds of organisms in the sealed bacteria farm, and we should actively mutate more species in for fun and sport... except that one time we do it for the evil disease of death. Said disease should be able to travel through the glass container without making a path for other stuff to leave. We should also have some pet animals nearby to catch the disease and spread it. We should also watch the diseases and bottle anything the disease god would like in a vial labeled "For Epan". If we can find him, we can show the stuff off to him. He is probably fascinated by that kind of thing, plus it throws off suspicion.
I dedicated an entire text wall to a war plan, but I get the feeling the GM wants us to be diplomatic. This is a long plan with many points at which things can go wrong. Curveballs are to be expected. Curveballs at certain points could mean death. I say we try to build up power in legitimate ways before even starting the above plan, so as to give us enough belief for the ultimate backup plan - RUNNING AWAY. I doubt the Escali will care much for what we do to the humans so long as we don't do the same to them. I get the sense they're that kind of race. They will be a little more suspicious of us, though. Also note that Valahun isn't our only issue - there's a big, scary pantheon. We can try to convince some to join us, though that's enormously dangerous. Perhaps we can throw some invites around after the fact? Still dangerous cause of stupid backstabbers. Probably best to meet the various gods and figure out their loyalties. Could ask high followers of various gods how we can get in contact with them.
Edit: Possible gods we can recruit against Valahun:
Epan, god of disease. It depends on his personality - we really need to meet him first.
Lostaki, god of death. Again, personality. If he hates the god of life, that's another plus.
Shen, god of entertainment. If he has the right personality, he should love the chaos we bring about and want to see what comes next.
Formod, god of politics. If our plans go without a hitch, then it should be politically advantageous to join us. Plus, we can use him for fake diplomatic talks with Valahun about us letting him back into power. Such discussions could be excellent time-wasters as well as focus grabbers.
Dregith, god of ice and the north. He is somewhat a foreigner in addition to being a new god. He may have little to no loyalty for Valahun. Should meet him personally.
Some other gods may be worth talking to, including the god of the unknown, though I don't know if we can trust them. We should have direct command over the idols such that we can make them work on followers of gods who side with us, though we should keep a careful eye on such gods. They may be Valahun's only hope for a retakeover if we can get this far, since they'll have belief gains. Should also keep a careful eye on Mr. politics, cause he can turn. We could also ask the god of diplomacy to join us, though he's known as the trickster god for a reason. If we can claim our intentions are to become a major god, and not to destroy/take over the pantheon, we might be more likely to get followers. Also if we will fight to get ally gods higher positions. Then again, the threat of us killing all of the pantheon that doesn't follow us can also be helpful in getting help.