Is it possible to define hook functions in template.php instead of the module?
Yes, you can implement any alter hook in a theme, as well as  hook_theme() and preprocess hooks.

Adding $form_state['redirect'] won't do anything there, though. You need to do that in a submit handler:

function MYTHEME_form_phone_book_node_form_alter(&amp;$form, &amp;$form_state, $form_id) {
  $form['#submit'][] = 'MYTHEME_phone_book_node_form_submit';
}

function MYTHEME_phone_book_node_form_submit($form, &amp;$form_state) {
  $form_state['redirect'] = 'go/some/where';
}


To ensure that your hook is running, get the Devel module installed and add dpm('alive'); in there. Then clear the caches (to be sure) and refresh the page a couple of times. If you don't see the debug message, the hook isn't being called, and it might be named incorrectly.