The default client, default relaying-transaction rules, and default mining rules are set to not allow tiny payments without a transaction fee. I've changed my client to allow all transactions of any output size without a fee, and on my testnet-in-a-box I could mine and send/receive transactions of 1 (or even 0!) satoshi just fine between my two computers that were set up with my client. (I was just testing this sort of thing for the fun of it and to get familiar with how the program worked; I don't really have any plans for using bitcoin this way.) So, if you could convince enough people on the main network, particularly miners, to adjust their clients accordingly, then you could do it on the main network too. The rules of bitcoin are basically done by consensus, in that having a lot of computing power lets you pick the rules to a certain limited degree. But I suspect that miners will always want to be paid *something* for tiny transactions, but you might find some that would find even a 1 satoshi fee to be enough to be worth the computational expense of adding it to a block (or at least prioritizing it over a free transaction), since it's better than getting paid nothing.
I think the biggest mining pool that follows rules for mining significantly different from the main client is
Eligius, which accepts any and all transactions that have a fee of at least 0.00004096 BTC per 512 bytes, even if the outputs are very small or non-standard. And there's a "
Free transaction relay" page on the wiki, suggesting that those nodes willing to relay all transactions connect to a central server so that miners interested in them will be able to get them. I don't know how many nodes are connected to it.
So there's some precedent that some large players may be experimenting with different policies, but for now, if you were to send a 1 satoshi transaction without a fee, it'll probably be quite a long time before a miner agrees to put it in a block.
