There are many ways to generate random planes and parishes for your game; this is merely one possible method.
The city of Dis always invades planes through urban areas, due to its sympathetic resonances with created spaces. These can be currently inhabited or long-since abandoned, such as vast ruins or tomb complexes. Consequently, it’s possible to generate both the parishes of Dis (the planes it’s already completely consumed) and the planes it is currently invading using the same method: they both involve fantastical urban locales.
Writing and then playtesting a set of tables for generating planes and parishes is an immense task, but luckily we can stand on the shoulders of giants. When you visit a new plane or parish, pick one of the themes on the following chart or roll-1 (with the result being a number 1-11, matching with the themes on the left side). Start with the first city with that theme, looking up the appropriate entry in Italo Calvino’s classic book, Invisible Cities, and using the entry to inspire your own vision of the locale. Color in the numbered circle to the left of the city’s name, to mark that it’s been used. The next time you pick the same theme, look up the next unused city.
Then, if you are visiting a parish, imagine how the place has been overrun and remade into a borough of Dis. What has persisted, in an altered form? What has been turned into something unrecognizable? What remains of the original inhabitants and how have they adapted? What people and institutions from other parts of the city have moved in?
Alternately, if you are visiting a plane, roll+0 to see how well it has resisted Dis’s advance. On a 12+, the city’s invasion has just begun and most of the residents of the plane have no idea. On a 10+, Dis has established a solid outpost in a single location; some natives are growing concerned. On a 7-9, the invasion has spread across the plane and its inhabitants faces dire choices about whether to attempt some dangerous plan or resistance or take action to preserve as much as they can before the inevitable end. On a failure, the plane is all but consumed and everyone there is struggling to deal with the fallout.
If Calvino’s description doesn’t provide enough sense of dynamism, suitably pro-active NPCs, or interesting situations for the PCs to become involved in, consult the “oracles” from D. Vincent Baker’s sword and sorcery game, In a Wicked Age, available online at http://www.lumpley.com/oracle/4oracles.php. The oracles named The Unquiet Past and A Nest of Vipers are probably the most appropriate for this game, but draw inspiration from Blood & Sex and God-Kings of War as you like.
For an alternate method of plane generation, you might try using the planet-generation rules in Kevin Crawford’s Stars Without Number, which is also available for free online.