How to search contacts with T9 dialer on Nexus 4
This is now a standard feature of Android 4.3, although you do need to enable it.

From http://www.android.com/about/jelly-bean/


  Autocomplete - just start touching numbers or letters and the dial pad will suggest phone numbers or names. To turn on this feature, open your phone app settings and enable “Dial pad autocomplete.”