There is only some thousands of nouns, not millions.
Most of them, around 80% (my estimation), follow an easy set of patterns. Like nouns ending with "e" are mostly feminim. An example list of them is here.
This reduces the nouns to learn to some hundreds, what is far from being impossible.
There are also various training apps to learn them, like Der Die Das.
Over these, you have no other way than experience.
This is much easier than it other languages (like French). In the everydays, making an article mistake makes your sentence sound badly, but native speakers have already accustomed to the foreigners regularly missing them.
Unfortunately, language exams tend to take this much more seriously as it is in the daily practice.
About the plurals, the case is roughly the same.
About the non-nominative articles: you have 2 4x4 matrices with many redundancy. This is not quite hard on the first spot. However, to automatize their usage, it has taken years to me. The problem is that they are very non-intuitive and in a verbal communication, you only have at most some tenth of seconds to determine the correct article.
Furthermore, you actually need two different skills:
- To automatically construct the proper article, depending on the gender and the case, while you are speaking.
- To identify the proper case, if you hear the article, knowing the gender.
In written communication, where you have time to think, it is far easier. But there are no wonders: you have the matrices, der-den-des-dem, die-die-der-der, das-das-des-dem, and so on. Learn them. Fortunately, this is very determinstic in German: if you know the gender and the case, the article will be always the same.