How to avoid Bitcoin-QT's transaction fee or change size limit?
You are probably trying to pay with BTC collected from very small payments (known as dust). This dust is commonly collected from advertisement sites. Though they know sending small payments will break your wallet this way, they just don't care as long as you keep clicking ads!

Since transaction size depends greatly on how many payments you're drawing money from, this generates a very large transaction which is very expensive both for miners and other nodes in the network. To reward miners for this cost you have to pay a fee or they will just refuse to mine/broadcast it.

Unless you pay this fee the transaction will be rejected by peers/miners, no matter what you do.

As a workaround you might want to consolidate all the dust sending smaller payments to yourself, but it's a tedious process, still has high fees and might not be possible depending on the concrete amount of payments you've received.