At a minimum. 0.0001 BTC per kilobyte. That would put you ahead of all transactions that are considered "low priority" which don't include a fee by all miners (and pools) that choose to use the reference implementation.
Given how low the exchange rate has been lately, you might even consider a fee of 0.0005 BTC per kilobyte. This would put your transaction ahead of everyone that is using the 0.8.3 reference implementation for fee calculation and even with everyone using the older versions. At the moment this works out to about 3.5 cents for an average transaction.