The circumstances under which case marking is "really necessary" can best be summarizes as "when otherwise most sentences become highly ambiguous and communication becomes impossible". In languages with fairly fixed word order and with prepositions / postpositions signalling certain grammatical functions, case marking could be dispensed with: in a strict SVO language "child sold cat" is unambiguous. In a strict SOV language "child cat sold" is likewise unambiguous. If you have free word order where all word orders are possible and equally likely, you can't rely on word order, so having case marking to distinguish subjects, objects, recipients and so on would be a good choice, communicatively speaking. Even so, given free word order and no case marking, there is little confusion over the meaning "cut child meat knife".
Case marking (in the normal understanding of the concept) is not even always required for free word order languages. In Khoekhoe, "basic" word order is SVO, but pretty much all word orders are possible. There is gender marking in the language: and the language uses gender marking to disambiguate. The subject has just it's own lexical gender; if you scramble an SOV sentence, the non-subjects have to also bear the gender marking of the subject (so any double marked NP is not subject).
Finally, a number of Bantu languages are pretty flexible with word order, but they have subject and sometimes object agreement. By matching the agreement properties of the verb, you can tell that ng'ombe akagura mwana means "The child (mwana) bought a cow" and ng'ombe ikagura mwana means "The cow (ng'ombe) bought a child", bizarre as the latter may be.
