It looks like itrasci has already addressed the question about 我. Here's some more information about 私.
Where the reading came from -- Derivation
Although we have the history of how watakushi has been used over the years, I cannot find anything definitive on where this term came from. The entry at Gogen Allguide suggests that there may be some connection between the initial wa- in watakushi and the wa reading for 我.
(Note that this wa appears to be a native Japanese term -- although modern Mandarin uses a reading of wǒ, which is pretty close to the Japanese, the older Chinese reading was something closer to nga, matching the Japanese on'yomi of ga but not the kun'yomi of wa.)
That said, there are no clear etyma (roots) that would fit. Assuming this initial wa as the first portion, there aren't any likely roots for takushi, or even taku + shi, or ta + kushi, etc. Neither wata nor kushi have anything likely. ("straw" + "comb"? Nope.) Ultimately, the origins for this term remain a mystery.
Update
The reading watakushi seems to predate Genji by at least two and a half centuries. I was poking around in the Man'yōshū and found watakushi used as a reading apparently meaning "private, privately owned" in poem 1275. A modern-Japanese rendering is available on this page.
How the meaning shifted -- Usage
私 with an on'yomi of shi still appears with a meaning of "private" in modern Japanese.
The kun'yomi of watakushi used to have this meaning too as the primary sense. In The Tale of Genji dating to the early 1000s, watakushi was used as an antonym of ohoyake -- modern 公【おおやけ】 "public". Some compounds using watakushi still have a meaning of "private" or "limited", such as 私雨【わたくしあめ】 "a rainfall in a very limited area", or 私金【わたくしがね】 "personal money", or even 私【わたくし】する "to make something private that was formerly public, to take something public for personal or private use".
This sense of "private, not public" developed over time to mean one's own personal, private affairs or thoughts, and from there, to oneself. Shogakukan's 国語大辞典 gives a citation for this use from 1632.
The various alternative readings -- watashi, atashi, atai, wasshi, etc. -- are all just phonetic variations of the older form watakushi (now regarded as the hyperpolite version of everyday watashi).
How pronouns move around in Japanese
Personal pronouns in Japanese work differently than pronouns in many other languages. "I" in English can be traced back to an ancient Proto-Indo-European root with cognates in umpteen other languages, and pretty much all of them share a similar meaning of "I" (first-person pronoun). Even Chinese's wǒ has been incredibly stable through the millenia, tracing back at least 2,500 years and possibly further back.
In Japanese, however, pronouns move and change in a much more fluid fashion. Historically, a term that may have started out as a humble indirect reference, such as 僕【ぼく】 (apparently originally meaning "servant", much like the super-polite English expression "[I am] your servant, madam"), degrades in meaning to become a very everyday, informal, and even rude term when used in the wrong contexts. 俺【おれ】 is now a term for "I" that is almost exclusively male, and is considered very informal and rude, but before the Edo period, it was broadly used by both genders regardless of social class or context.
There has been a lot of research into politeness in Japanese, and how indirection results in changes in pronoun usage over time. It's a very deep subject, and there's tons to read if you're interested. Here are some relevant links for starters.