You have to relay it directly to a miner who will mine non-standard transactions for you. It is impossible to get it propagated through the network if your transaction is non standard with the reference nodes not relaying it. I remember Eligius used to provide this service with their pushtx, you have to contact owners of the pools if you want to do it nowadays.
Eligius doesn't mine all non-standard tx, it has a precise set of rules (i read them one time, but can't find them anymore), i remember they don't accept any output below a certain amount of satoshi.
this is great find.,
looks like you can do transaction with 0 output and set the whole input as fee.
yes, it's a valid tx, but you have to find a miner who mines it