He wasn't sitting there writing binary code and implementing all 7 layers of the OSI stack by hand, he was was gluing together pre-existing components. And the pre-existing components he had access to include two major email startups acquired by Google in 2001 and 2003, which were founded in 1995 and 1997 respectively. (Although he does have at least two patents for features and algorithms he co-invented while making Gmail.)