Learn Polish: Widziałem go w zeszły wtorek.

Widziałem tells us the speaker is male. In the Polish past tense, verbs change their endings based on the gender of the person speaking. If a woman were saying this, she would use widziałam.

Why do we use go instead of jego for "him"?

go is the short, unstressed form of the pronoun. You use it in the middle of a sentence when you are just stating a fact without special emphasis. You would only use the long form jego at the beginning of a sentence or to put heavy emphasis on the person (like "I saw HIM, not someone else").

Why is there a w before "last Tuesday"?

In English, we say "on Tuesday" or just "last Tuesday", but Polish uses the preposition w (meaning "in" or "on") followed by the day of the week to express when something happened.

If this takes the Accusative case, why do zeszły wtorek look exactly like their basic dictionary forms?

They are actually in the Accusative case! Wtorek is a masculine inanimate noun (a thing, not a person or animal). For masculine inanimate nouns and the adjectives attached to them, the Accusative case form is completely identical to the basic dictionary form (Nominative).