This game is a good example of not blindly playing into "power" cards. They are not always the best strategy and even though in most cases Rebuild counters junkers pretty hard, there are always exceptions to the rule. Both the lack of Rebuild support and ability to open Cultist provide a unique board where Rebuild is actually not able to outpace junking attacks.
I'm not so sure this game is an example of that concept. Isn't Cultist considered more of a power card than Rebuild? "Blindly" playing into this would actually not turn out wrong. I would guess the best strategy is going Cultists into Rebuilds (assuming your opponent also goes Cultist -- if not, just go money and Provinces, like you did), which seems like the most obvious thing to do.
According to SCSN's simulation results, pure Rebuild-BM does beat Cultist-BM. On this board, Altar helps both a Rebuild and a Cultist player, but it also counters Cultist by trashing Ruins. The starting coin token should slightly help Cultist for whom early gains are more relevant. But Navigator and (probably) Moneylender are good support for Rebuild, and there's no Shelters or Colonies, so I think I'd go Rebuild-BM (gaining an Altar with the first $6, saving my coin token for this buy) on this board.
(Apart from not saving his coin token and not buying Moneylender before Rebuild on T1, shark_bait's opponent was unlucky in that his first Rebuild misses the reshuffle, and the first time he gets to $5 "on his own" was only turn 6.)
B) If you go for Rebuild, I think the opening to do is Moneylender/Navigator over Silver/Navigator. Yes they are two terminals but you're keeping your deck thin and you can always pick out the good hands for Rebuild (and pick up an Altar when getting $6).
Sacrificing a coin token for a second $4 card which may easily collide on T3/4 seems suicidal to me. Unlike Cultist, Rebuild doesn't care much for keeping your deck thin anyway, a thin deck increases the risk of collision with the only rebuildable VP card. Save the coin token for a $5 or $6 buy instead.
My gut feeling says B) is way too slow. So I think A) is the call here. And of course when the ruins are dealt out, you can always switch to Rebuild yourself.
With a Cultist chain running, you'd draw Rebuild dead half the time (and with the other half, you have to Rebuild your less profitable starting Estates first). Witch into Rebuild is better than either card alone, but I'm sure Cultist into Rebuild is worse than either single-card strategy.