Go to System Settings -> Keyboard. Under the "Shortcuts" tab, go to "Custom Shortcuts". Create a new entry named "Launch Terminal Fullscreen" (or whatever), and enter the following as the command:
gnome-terminal --window --full-screen
You're supposed to be able to click on that entry and then press the key combination you wish to use in order to set the new keyboard shortcut, but for some reason, that wasn't working for me. If that's the case, you might need to edit the launcher shortcuts manually...
According to this page, the keyboard shortcuts for Unity can be found at:
Each keybinding seems to be in a separate folder, named "custom0", "custom1", etc. Edit the "%gconf.xml" file found in one of these folders which contains the keyboard shortcut definition you just added in the "Settings -> Keyboard" dialog, (if you added one). Here's mine, mapped to "CTRL-ALT-m":
<entry name="action" mtime="1381112788" type="string">
<stringvalue>gnome-terminal --window --full-screen</stringvalue>
<entry name="name" mtime="1381112788" type="string">
<stringvalue>Launch Terminal Fullscreen</stringvalue>
<entry name="binding" mtime="1381110910" type="string">
I suppose you could try just copying the above into a new file named "%gconf.xml", and putting it in a new folder named "customX", (where "X" is the next available number), in the
~/.gconf/desktop/gnome/keybindingsfolder. I haven't tried this, yet.
After editing the XML by hand, I logged off and logged back in in order to force a re-scan of the keybindings, and voila!