How were Chinese characters taught to Chinese children before the introduction of pinyin?
In the (very) old days, there was a system called 反切 (in English) where two characters were used, one for initial, one for the rhyme (vowel[s] + final), followed by 切 to indicate it was a phonetic notation. For instance, 東 could be represented as 德紅切.
Edit #2
I thought I should insert an example from the canon of Chinese dictionaries, 康熙字典. Here's page 1 -- might as well start at the beginning...

I highlighted the two definitions for 一: 於悉 for 唐韻 and 韻會, 益悉 for 集韻 and 正韻. Which is interesting, as these won't match the modern pronunciation in most dialects (strangely enough 於悉切 works perfectly in Hakka for 一 but that's probably more likely an accident...).