I doubt this is the only possible solution (it may not even be the best), but I think it works reasonably well for your two examples.
The passive of videre can be paired with the future active participle to indicate the outcome that's anticipated (even if only by the speaker). This construction is amply attested, being found in Cicero, Livy, Seneca, Tacitus, and others. Here are just two examples:
Cicero, Epistulae ad Atticum 15.11.2:
sed et Cassius mihi videbatur iturus (etenim Servilia pollicebatur se curaturam ut illa frumenti curatio de senatus consulto tolleretur) et noster Brutus cito deiectus est de illo inani sermone <quo se Romae> velle esse dixerat.
'…Cassius seemed to me (to be) about to go…'/'…it seemed to me that Cassius would go…'/'…Cassius seemed to me likely to go…'/etc.
Tacitus, Historiae 3.78:
quidam omnium id ducum consilium fuisse, ostentare potius urbi bellum quam inferre, quando validissimae cohortes a Vitellio descivissent, et abscisis omnibus praesidiis cessurus imperio videbatur:
'…he [Vitellius] seemed (to be) about to abdicate'/'…it seemed that he would abdicate'/'…he seemed likely to abdicate'/etc.
For your examples, the clause that expresses the anticipated outcome can then be attached as a concessive subordinate clause to a main clause that expresses the actual outcome.
cum Caesar victurus videretur, demum tamen victus est.
Although it seemed that Caesar would prevail/was certain to prevail, in the end he was defeated.
etsi moenia casura videantur, deis tamen potentibus manebunt.
Even though it seems that the walls will fall/are certain to fall, they will endure if the gods are powerful.
Alternatively, in theory, since the actual outcome for your first example is in the past and the anticipated outcome has been proven false, you're dealing with a contrafactual situation and could do something like the following sentence from Livy (Ab urbe condita 5.26.10):
videbaturque aeque diuturnus futurus labor ac Veiis fuisset, ni fortuna imperatori Romano simul et cognitae rebus bellicis virtutis specimen [et] maturam victoriam dedisset.
And it seemed that the toil was likely/certain to be as long-lasting as it had been at Veii, (and it would have been too) if not for the fact that fortune gave the Roman general....
Nevertheless, meaning-wise, I have to admit that this approach doesn't work particularly well for your example – or at least it isn't a very satisfying sentence:
Caesar victurus videbatur, ni demum victus esset.
It seemed that Caesar would prevail/was certain to prevail, (and he would have done too) if not for the fact that he was defeated in the end.
