Less capital now than ever. Local service businesses like "Mop It Up" would cost almost nothing to operate. The barrier to entry is simply that the work is undesirable. This makes it valuable.
So even with janitorial work, an educated graduate can turn it into a profitable business, without actually doing the cleaning himself.
Edit: his site is http://www.maidsinblack.com/ and he does a great job of documenting his startup experience step by step on reddit. If I find the thread, I'll post it here.
Anyway, this kind of business would have been possible in the past with local newspaper ads and the Yellow Pages.