Human ingenuity always finds a way. In Chinese dictionaries, there are simply multiple indices: you can look up characters by pronunciation (if you know the word but not how to write it) or by shape (if you know the character but not how to say it). The latter works because there is a small set of shapes (“radicals”) that are combined to produce new characters.

I can't speak directly to Chinese, but I am studying Japanese, which has a writing system derived from Chinese. Essentially each character can be broken up into smaller components (called radicals). This allows characters to be ordered somewhat 'alphabetically'. In theory, the radicals also carry some sementic and phonetic meaning, although (at least in Japanese) many characters have deviated significantly from what you would expect from the roots.

Also, although Japanese has been (through deliberate effort) simplified to about 2,000 characters needed to be considered literate, it still takes until high-school for students to be able to fully read and write all 2,000.

(Disclaimer: Not to argue for who invented computers first.)

Yeah, there is a famous computer geek who invented a super nice Chinese input method named "Cangjie" in Assembly and it can be used with a special Chinese CPU. (Now he is an old man.)

https://en.wikipedia.org/wiki/Chu_Bong-Foo

Two ways. If you know what it sounds like, you look in the phonetic index, which is ordered alphabetically according to the pronunciation; if you know what it looks like, you can look in the radical index, which lists characters by their radicals, ordered by how many strokes they have.

To answer your question on looking up a character in a dictionary, there are 3 ways, which are 3 indexing systems, all present in a dictionary. One can decide which index to use, either based on its pronunciation or its composition.

Largely, they don't, without a great deal of training. http://pinyin.info/readings/texts/moser.html