I guess a short, and somewhat cold, answer might be that it's actually logistically very difficult to organise the systematic destruction of an entire religion. So the solution was "final" in the sense that, before then, Germans tried to get rid of Jews and other 'undesirables' in other ways, say by encouraging Jews to leave the country* or just shooting the ones you come across.
I guess, if it was ever planned in advance, maybe Hitler et al preferred to wait until they could deal with the entire "Jewish problem" at once, as in when they controlled mainland Europe.
*Incidentally, Ken Livingstone was therefore technically right when he said that Hitler supported Zionism, but it's a pretty stupid thing to say without context: it's transparently obvious that Hitler's support for a state of Israel was to get rids of the Jews in Germany for his own benefit, rather than theirs, and to therefore claim that he was a Zionist is just offensive. I mention it here only to disassociate myself from such a pathetic reading of history.