Here are some possible solutions to this problem that haven't been listed already.
- mark case with tone or another suprasegmental feature
- case disfixes
- have a large class of indeclinable nouns
- achieve free word order via noun classes and agreement
1 Case Tone
Maasai marks case with tone. It's predominantly VSO, but frequently uses VOS order if the object is more topical.
2 Case disfixes
Some languages like Alabama (Muskogean, North America) delete phonemes in a root to indicate pluractionality (plural subject/plural object/multiple repetitions), basically verbal number. You can repurpose this feature for case.
Here's a strawman example in a 3-case language (direct, oblique, and genitive).
direct case: unmarked
oblique case: delete the final phoneme
genitive case: delete the final 2 phonemes
chopal means house.
to/from/&c the house chopa
the house's chop
3 have a large class of indeclinable nouns
You can have a fair number of nouns that don't decline at all before the declension system breaks down completely.
Indeclinable nouns can end in whatever you want them to.
This might work well if your language has optional prepositions or postpositions with the same meaning as certain cases so that the role of an indeclinable noun can be clarified if necessary.
4. noun classes and agreement
Some languages such as Swahili have many noun classes and require verbs to agree with their arguments. Many Bantu languages like Swahili have agreement with direct objects as well, but don't require its usage in all situations.
You can also achieve the same effect with obligatory clitic doubling, such as in Macedonian. The idea is that you must have a pronoun referring to various verb arguments (such as the direct object) even when a full noun phrase is present. Clitic doubling is more effective at disambiguating sentences if you have more noun classes or more grammatical numbers.