Take an example like TaskRabbit. Using Jeff's suggestion that you start manually, I would suggest:
1) Start providing the services yourself by advertising your ability.
2) Grow the business to a point where it makes sense to have a technology solution as an intermediary because it's getting too hard to manage yourself.

Not only do you validate the need with the customer, but you've figured out how to make money in the process.