Same for the intellectual first sentence of Confucius' Analects 子曰: 學而時習之, 不亦說乎? And of course people would also study other texts that would introduce them to additional vocabulary.
Your character count for the Shouwen dictionary is way off, it has less than 10000 distinct characters, and its primary purpose wasn't to provide obscure characters for use in new texts, but to provide easier-to-understand definitions for characters found in old texts. A tool to ease understanding, not hinder it.
I'm not sure which of Lu Xun's essays in particular you're referring to, but in general his beef was with the continued use of literary Chinese, not that people weren't being taught enough characters to write in it.