In the many cases in my life where it wasn't so, here is the method that worked for me:
1) Divide the tasks into small enough bits that there # tasks / # people >> 1
2) Assign tasks at random
3) Let people trade and make it easy for them
This is statistically fair (which is enough in practice in every occasion I've had to solve a division of labor problem) and maximizes utility, which is a lot more important (this means the generalized version of "every task will be performed by the person that is least averse to performing it").
I'm still waiting for a good generic tool to do this, I lately toyed with the idea of releasing a Google Spreadsheet app
Ie everyone starts with a 1/n chance of having to do task 1 and a 1/n chance of task 2. Alice might want to trade away her chance of having to do task 1 in exchange for taking on more risk of having to do task 2.
I actually wrote a tool that plans oncall shifts like that for Google's Site Reliability Engineering when I was working there. There's some nice economic theory for how you have to organise the auction to elicit honest preferences---so that you can run the whole thing in a computer completely automated instead of actually having to wait for people to do the haggling manually.
(If you don't do that step, your haggling only after the random assignment is likely to be more practical.)
See "Elicitation of honest preferences for the assignment of individuals to positions" (http://www.eecs.harvard.edu/cs286r/courses/spring02/papers/l...). The main result you get from the paper is that it proves a relatively simple single linear optimization model to figure out the assignments of tasks correct and incentive compatible.
So fair it makes the whole architecture serverless!