Lookup will accelerate over time. For example, while the characters are non-phonetic, there are many characters with the same pinyin (minus the tones). Just by looking at a character and noticing that it is similar in shape to one you already know the pinyin for, you can often guess that the pinyin will be the same. For example, "据 剧 居" are all "ju" (with different tones) in Chinese, so by knowing one, you can easily look up the other two. There are probably even more, but these are the 3 I'm familiar with at the moment.

Another option would be to watch Chinese or Japanese TV programs, either on DVD or computer so that you can pause and rewind. Almost all Chinese TV programs are subtitled, so you can hear the pronunciation and use that to look up the character if it is unfamiliar.