To accomplish what you want, you'll have to edit the source code for gnome-terminal and rebuild it yourself, as the minimum window size is hard-coded into the terminal application. To do this, follow these steps.
First, go to https://launchpad.net/ubuntu/+source/gnome-terminal/3.6.1-0ubuntu4 and download the source files (the file is gnome-terminal_3.6.1.orig.tar.xz). Download this to your ~/Downloads folder.
Then, open a terminal and type the following commands:
cd ~/Downloads
tar -xJf gnome-terminal_3.6.1.orig.tar.xz
This will extract the source. Now, open up your favourite text editor and edit the file ~/Downloads/gnome-terminal-3.6.1/src/terminal-window.c. Navigate to line 3107, where you will find the variables MIN_WIDTH_CHARS and MIN_HEIGHT_CHARS. Edit these, these are the minimum height and width of your terminal window expressed in characters (i.e. a MIN_WIDTH_CHARS of 20 will mean that you can no longer resize the width of the window to below 20 character widths)
Then, to build, in a terminal type cd ~/Downloads/gnome-terminal-3.6.1. Then, run ./configure to generate the makefile (if it complains about any missing packages, install them using apt-get (e.g. if it says "package foo not found" or similar, use sudo apt-get install foo). You can also try installing auto-apt and using sudo auto-apt run ./configure (this will attempt to install all dependencies), but when I tried this it didn't quite catch everything (run standard ./configure afterwards) This may take a few attempts, depending on how many packages are missing.
Once it has generated the makefiles simply type make, followed by sudo make install. This should rebuild the terminal program.
Close all terminal windows, and then the next one you start will respect the minimum size you set in the source (i.e. will not resize below the values you defined there).