"Last Wednesday I went running with my girlfriend."
In English you absolutely can say "I and my girlfriend went running." It's just a little bit unusual. You can also say, "It was just my girlfriend and me." You use "I" when you're the subject of the sentence and you use "me" when you're the object of the sentence. Nothing to do with what order.
You are more right than you know. There are actually three distinct grammatical points here.
Other-and-self order is 'right', self-and-other order is 'wrong'. Frankly, this is a BS rule that social climbers made up in the late 1800s so they could distinguish their own class (who had time to waste artificially changing the way they talked) from poor folks (who did not). Since then, of course, it's been working its way into the language ideology of the people it was meant to exclude. But when ideology doesn't interfere, natural English still chooses its order based on the rhythm of the phrase and on which parties have already been mentioned in the discourse, not on self vs other.
I/she/he/we/they vs me/her/him/us/them in noun phrase conjunctions. This is a slightly less recent, slightly less BS rule that comes from scholars naively forcing English into the mold of Greco-Latin grammar. Greek and Latin, the only languages whose grammar they could explicitly describe, use the same pronouns for conjoined noun phrases as for standalone ones; if they only grammars they had studied did it that way, that must be how Grammar Itself works (here insert snarky comments about Noam Chomsky & Co.), and English would therefore obviously do the same.
Object vs subject complement. If we're fully committed to imposing Latin grammar on English (and some people still are), we must say "It was just my girlfriend and I." The phrase that's required to complete is/was/am/be/etc. has the semantics of a predicate, not a direct object (this is true in English as well as Latin). In Latin, it takes the nominative case ("I/she/he") because in Latin, that is the unmarked, default form.
So why did you write "It was just my girlfriend and me" then? Well, because you speak English, and it turns out English is not just Latin in borrowed clothes. In the spontaneous speech of native English speakers, I/she/he is clearly a special, marked form; the unmarked form is the me/her/him one. Exactly when it is appropriate to use the marked form varies a little from speaker to speaker, but nobody naturally reproduces the Latin usage.