I finally found a minimal, simple, non-intrusive way to get Taiwanese input on Gnome:
apt-get install scim-chewing im-switch
Then, as a user:
im-switch -s scim
Then log out and in again. It should work. If it doesn't, then you need to tell pango to use SCIM: right click wherever you have the cursor, choose "Input method" and then "SCIM".
There! It works!