**EDIT:** Also refer to [Aminopterin's answer][1] for a different insight.

----------

After some research, I found two reasonable explanations. But, IMHO, the two should be compiled as the following:

> **老** is a prefix that is added to make **虎** and **鼠** easier to pronounce; besides, it implies that people respect **虎** and fear **鼠**.

The two explanations as follow:

----------

##Affix for smooth pronunciation##

In the Classical Chinese era, texts were concise and some, if not most, of the words were one-character words. Yet, in colloquial context, people prepended/appended affixes to make the words easier to pronounce. These "new" words then became widely accepted and conventional. 

Some common affixes and their associated words:

 - **子(suffix)**

> 獅子、兔子、鴨子、猴子、鏡子、桌子、椅子、房子、筷子、刀子...

> lion, rabbit, duck, monkey, mirror, table, chair, house, chopsticks, knife...

 - **老(prefix)**

> 老虎、老鼠、老鷹、老師...

> tiger, rat, hawk, teacher...

 - **頭(suffix)**

> 甜頭、苦頭、舌頭、骨頭、石頭、木頭...

> sweetness, suffering, tongue, bone, stone, wood...

##Affix with connotation##

In Chinese, `老`, apart from `aged/experienced`, has the implicit, figurative meaning of `respected` because people respect elderly so as to comply with the social value. That said, people prepended `老` on the ones they respect. This is why `老虎` and `老師` are named the way they are.

`老鼠`, on the other hand, has various interpretations. Some state that it fits to literal meaning of `老` – `old`. According to the `Compendium of Materia Medica(本草綱目)`, a medical book, rats have the longest life span. Such misunderstanding came from the impression that rats have a high 
rate of reproduction and have been around people back then for the longest time. 
Some argue that the `老` in `老鼠` implies the cunning characteristics of rats. This interpretation can also be applied to `鷹`. The rest argue that people chose `老` for `老鼠` to imply their fear toward rats and that rats are not easy to deal with.

As to why `獅` is named `獅子` but not `老獅`, the reason is intuitive – to avoid conflicting pronunciation with `老師`.  


  [1]: http://chinese.stackexchange.com/a/22023/9722