A clause introduced by "before" can be used as an adverbial clause. It doesn't have to be. It can also be used as an adjectival clause. In the example sentence, it is adjectival. Consider this example:
The time when flesh was many different colors was a time before we went to Sameness.
Here, the function of "before we went to Sameness" is the same as the function of "when flesh was many different colors". In the sentence above, they each directly modify an instance of the noun "time".
In the original example, it still modifies an instance of the word "time"*, but it does so indirectly, as licensed by the copula "was" and indicated by the demonstrative "that".
Yes, the structure of the sentence in question is subject / verb / complement. More specifically, it's subject / copular (or linking) verb / predicative adjectival subject complement.
Different frameworks label things in different ways. Traditional grammars are more likely to label this "before" as a subordinating conjunction. Modern grammars are more likely to label this "before" in the same way as they label the "before" of "before noon" -- as a preposition.
Q: Is "before we went to Sameness" a predicative complement in the example sentence?
A: Yes, it is. It acts as the argument of the predicating verb "was".
Q: Is "before we went to Sameness" an adjectival complement in the example sentence?
A: Yes, it is. It acts as a modifier of the subject. A nominative complement would act as a separate reference to the subject's referent.
Q: Is "before we went to Sameness" a subject complement in the example sentence?
A: Yes, it is. The constituent that it modifies is a subject, not an object. Specifically, it modifies "that".
Q: Is "before we went to Sameness" a complement in the example sentence?
A: Yes, it is. We can identify the constituent that licenses this constituent. In this case, "before we went to Sameness" is an argument of the verb "was". We can also identify the constituent that this constituent complements. In this case, "before we went to Sameness" complements the subject "that".
_______________
* If we wish, we can go a bit further down the rabbit hole: the adjectival clause modifies an already-modified instance of "time", since the demonstrative "that" refers to the entire content of "a time when flesh was many different colors".