17th century borrowing (maybe from Tatar?) Ironically, likely originally an Indo-European word: https://en.wiktionary.org/wiki/%D1%82%D1%83%D0%BC%D0%B0%D0%BD
не было is just the past tense of the verb нет (= не есть) Non-existence calls for genitive.
General rules are tough to come by. This is actually an area of Russian grammar that's experienced noteworthy change in the past century or so. Genitive used to be more common in negative sentences than it is now.
Thank you for the "не было" AND нет (= не есть) information, that now makes a little sense :)
In my opinion, generally, Russian grammer is not so strict when we compare it with English (also a foreign language). I know that genitive is not mandatory here, but I have to give a little care to use the language correctly
What is presented as genitive in the link is probably the partitive case, a rare grammatical case used to express the quantity of sth. It has been almost entirely replaced by the genitive except for certain nouns where it is still applicable. Duolingo has a lesson about that quite early on within the tree, it doesn't include a lot of practice on the actual partitive case but it explains a little about it.