How do faucets/micropayment-based services avoid/minimize transaction fees? Sites like bitvisitor or cointube give away very small amounts of bitcoins (I actually got a payment as small as .0000035 BTC when testing).
I am in the process of creating a service that awards users small amounts of bitcoins in exchange for doing some trivial work (akin to Amazon's Mechanical Turk). When experimenting, I tried using bitcoin-qt to send .0001 BTC to an address and it automatically added a .0005 fee onto it. Using Electrum, I couldn't get it to send until I set the fee to .0001 as well. 

I highly doubt a fee like that was paid for the .0000035 BTC I received earlier), so how are these services eliminating or minimizing their fees? I know it's common to gather multiple "inputs" into a single transaction. Is it possible also to have a transaction with multiple outputs so that I can gather a hundred of these .0001 BTC payments into a single transaction and thus minimize the size (in kb) of the transactions and therefore the fees too?

EDIT
Sites like BitVisitor do indeed combine these payments (see here). So assuming there's no better way to minimize fees, how are they able to do this? I see no options in bitcoin-qt or Electrium for this.
You have two questions here, so I'll answer them separately.  As far as how do faucets they avoid transaction fees, the answer is that they don't.

Most of the faucet sites I've used use a service called Coinbox.me which collects requests for payments and bundles them up into one large chunk of payments.  This is how they minimize transaction fees - they don't send all the microtransactions at once, they wait until they have quite a few and then send them out.  I've looked at these transactions before when they're going through and they do have transaction fees that are being paid that is, as you said, larger than the amount being sent out.  But I have had transactions where it is being sent to at least a hundred addresses, so while one small amount may far less than the transaction fee, the total amount being sent out is significant enough that the service can pay a transaction fee while still paying out these microtransctions.