Edit: not anymore applicable for Ubuntu 16.10 and newer

Finally figured it out.. first sudo apt-get install dconf-tools nautilus-open-terminal, then run dconf-editor and set the org/gnome/desktop/interface/can-change-accels boolean on. Then open nautilus using this command (to disable Unity global menu Temporarily):

nautilus -q

UBUNTU_MENUPROXY=0 nautilus

Now you can mouseover the action in the file menu, and change the accel by typing your key while the action is highlighted, finally restart your nautilus. If you don't see Open in terminal in the File menu and you've just installed nautilus-open-terminal, you might need to first run nautilus -q.

Ubuntu 14.04 and up

If you can't find the can-change-accels key in your dconf configuration you can try the following solution:

1. Stop nautilus by executing nautilus -q

   
   



2. Open ~/.config/nautilus/accels in a text editor of your choice, e.g. gedit:

   
   

    gedit ~/.config/nautilus/accels
   
   

   
   



3. Try to see if you can find the following line:

   
   

    ;(gtk_accel_path "<Actions>/DirViewActions/OpenInTerminal" "")
   
   

   
   



4. If the line exists, add your keyboard shortcut in the second double-quoted segment and uncomment the line by removing ;:

   
   

    (gtk_accel_path "<Actions>/DirViewActions/OpenInTerminal" "F12")
   
   

   
   

   This would set the shortcut to F12. For a list of all possible key codes please consult this answer.

   
   

   If the line doesn't exist just copy and paste the one found in this answer at the end of the file.

   
   



5. Save the file and restart Nautilus by clicking on the Nautilus icon in your launcher/dash.

   
   

Ubuntu 15.10 and 16.04

Here, the relevant command in ~/.config/nautilus/accels is TerminalNautilus:OpenFolderLocal. (NautilusOpenTerminal::open_terminal is still present in the file, but doesn't seem to have any effect.) So follow the instructions above, except change the line

; (gtk_accel_path "<Actions>/ExtensionsMenuGroup/TerminalNautilus:OpenFolderLocal" "")

to

(gtk_accel_path "<Actions>/ExtensionsMenuGroup/TerminalNautilus:OpenFolderLocal" "F12")

to make F12 your keyboard shortcut. Notice that ; is again removed.

Finally, log out for changes to take effect.