Some languages don’t even use word order as the primary mechanism for forming sentences. Latin and Ancient Greek are two examples. They are “inflected” meaning you change the word to show how it functions in a sentence.

Pronouns in English still function this way a little (for example he = subject, him = object).

Are you describing case systems/declension here?

Seems so.

Just for your curiosity, my favourite explanation of Japanese sentence structure is that it is an outside in language, where English is inside out. Since Japanese doesn't follow a conrete word order like SVO, it was very helpful to see it that way.

The kids had lunch in the park at 12pm today.

vs

The kids, Today at 12pm in the park had lunch.

The grander more ephemeral concepts go first in Japanese, with some common exceptions (persons tend to go at the start as it does in the example). In English we tend to start with the closest concept and work our way out.

That really helped my understanding and sentence creation.

Yep. Take German for example. Any subordinate clause puts all verbs at the end in reverse order (SOV; it used to be all clauses but as with many languages it started to shift toward SVO).

    I like cats, because cats like me.

translates to

    Ich mag Katzen, weil Katzen mich mögen.

which directly translates to

    I like cats, because cats me like.

This is a simple example but gets sufficiently complex as the sentence does. All of the verbs get pushed to the end, which as an English speaker means you have to mentally construct the sentence first and know which verbs you need to use prior to using them.

It gets further complicated because verbs also change the tense of the sentence, which ultimately dictates which articles to use (der/die/das/den/des/etc. - all meaning "the" - or ein/einen/eine/eines/etc. - all meaning "a").

And yes, native speaking Germans screw it up all the time, too. Just like English speakers mess up "a" and "an", "me and my friends", "your/you're", etc.

What makes you think that native German speakers screw it up "all the time"? I'm German and I did not encounter any of these mistakes in years, despite being a grammar nazi.