[To the OP: I'm not trying to pick on you personally, but raise your and others' awareness of thinking about the logic of the question(s) asked on SE and elsewhere. Please don't take this personally!]
The title of the question is good, but you are severely limiting the scope of your answers by including '... situations where they needed compile-time code generation.' Many good answers to the question about how to do compile-time code generation in C++ without templates exist on this page, but to answer the question you originally posed:
What did people do before templates in C++?
The answer is, of course, they (we) didn't use them. Yes, I am being tongue-in-cheek, but the details of the question in the body seem to (perhaps exaggeratedly) assume that everyone loves templates and that no coding could ever have been done without them.
As an example, I completed many many coding projects in various languages without needing compile-time code generation, and believe others have also. Sure, the problem solved by templates was an itch large enough that someone actually scratched it, but the scenario posited by this question was, largely, non-existent.
Consider a similar question in cars:
How did drivers shift from one gear to another, using an automated method which shifted gears for you, before the automatic transmission was invented?
The question is, of course, silly. Asking how a person did X before X was invented isn't really a valid question. The answer is generally, 'we didn't do it and didn't miss it because we didn't know it ever would exist'. Yes, it's easy to see the benefit after-the-fact, but to assume that everyone was standing around, kicking their heels, waiting for automatic transmission, or for C++ templates, is really not true.
To the question, 'how did drivers shift gears before the automatic transmission was invented?' one can reasonably answer, 'manually,' and that's the type of answers you are getting here. It may even be the type of question that you meant to ask.
But it wasn't the one you did ask.
Q: How did people use templates before templates were invented?
A: We didn't.
Q: How did people use templates before templates were invented, when they needed to use templates?
A: We didn't need to use them. Why assume we did? (Why assume we do?)
Q: What are alternative ways to achieve the results that templates provide?
A: Many good answers exist above.
Please, think about logical fallacies in your posts before you post.
[Thank you! Please, no harm intended here.]