This drove me crazy for nearly two years. On my Ubuntu 14.04 installations, I was not able to set the default encoding for my terminal to utf-8, no matter what I set my environment variables to. Instead, all terminals would start up with the encoding set to the current locale's, which in my case was ANSIX3.4-1968. At the end, the two different solutions worked for me.
Set locale environment variable
Put this in your /etc/environment file. Create the file if it doesn't exist.
Apparently gnome-terminal will pick up locale before your bash profile files load, so you'll need to set LC_ALL somewhere pretty early in the boot process.
If that doesn' work,
Set gnome configuration value
You can alternatively set the default encoding for gnome-terminal explicitly using conftool:
gconftool --set --type=string /apps/gnome-terminal/profiles/Default/encoding ISO-8859-1
I hope this saves somebody out there some frustration in trying to figure this out.