The method I used was to persuade a friend into trading a Starveling Cat back and forth (the cat was not happy) until I reached level… 2, I think. From then on I could attend the Duchess’s salons and speak of terrible things to increase the quality by myself.
The benefit of these routes is that you need neither Fate nor importance. However, I believe you do need some paltry amount of connections with the Duchess to unlock the latter option.
edited by Felicity Chase on 2/13/2012