I tried using "qtconfig" but that didn't help. (Even changing the style in Skype, then using Qtconfig won't show any effect.)
Where could I make the fonts larger? (Ubuntu's accessibility settings won't affect it either.)
You can do it through qt4-qtconfig. Install it as Eliah Kagan suggested. What he missed, though, is that you have to change the style.
So, when you run qtconfig, choose Gui Style to be Cleanlooks (for example), then save. Restart skype, and the new fonts will be applied. This does not work if the style is Desktop Settings.
Open Skype, change the style -> cleanlook. Close it.
Open a terminal and sudo apt-get install qt4-qtconfig .
After that open Qt 4 Settings, change fint size, select cleanlook, save and exit.
Open skype again and voila :)
I tested this in Linux Mint 14 Mate. It should work in Ubuntu too, though.