In ZSH; this can be achieved by adding this to the .zshrc
setopt debugbeforecmd
trap 'if ! whence -w "$ZSH_DEBUG_CMD" >& /dev/null; then special_function $ZSH_DEBUG_COMMAND;fi' DEBUG
exec 2> >(grep -v "command not found" > /dev/stderr)
This will behave in a very weird way in bash; because bash sends the prompt to stderr ( In effect you will be able to see the prompt and anything you type only after pressing the Enter key ). ZSH on the other hand, handles the prompt and stderr as separate streams.
If you can find a way to make bash to send the prompt to some other location ( say /dev/tty ) something similar will work in bash also.
EDIT :
It seems that bash versions > 4 have a command_notfound_handle
function that can do what you want. You can define it in your ~/.bashrc
command_notfound_handle {
special_function $1
# The command that was not found is passed as the first argument to the fn
}