TPC Fax is a free service that lets you send text faxes by email. It doesn't have a huge international coverage, but it works for most big cities.
To send a fax, you need to drop a mail to:
remote-printer.recipient_name@fax_number.iddd.tpc.int. For details about the syntax, go to this page
Adrian Hristov, who sent me this tip, has an interesting idea: what if you forward all your mails from Gmail to a fax number using this service? You could also use a filter to forward only some of the mails.