If I said "I" was "Zha" would it be plausible to say "you" is "Zho" and from there naturally begin forming grammatical gender, or would that be too early in the language to add complexities? Also, could the word "we" not be a root word but instead be derived from "I" (Zha->Zhasa)?
Sure. And like always, real languages got there first.
In Quechua, for instance, fist person singular ("I/me") is Ñuqa. 1st person plural inclusive (we, all of us) is Ñuqanchik, and exclusive (us, but not you) is Ñuqayku.
Second person singular is Qam, plural Qamkuna. Third person singular is Pay, third person plural Paykuna. -kuna is simply the Quechuan plural suffix. "House" is wasi, "houses" wasikuna.
"You, the person I'm talking to" Qam, "You, the people I'm talking to" Qamkuna.
It's quite common in many languages that "I" and "you" are distinct; after all, I'm usually the most most important person in the universe, and you just live there. Third person pronouns seem to often be derived from pointing words: "that thing over there" becomes "that person over there".
It looks to me that I, you, and he/she are typically not derived from one another. So Zha "I" might typically be quite different from the word for "You". But beyond that, inflecting these base pronouns is certainly fair game.
English I and you, for example, are unique as far back as we can go (Proto Indo European).