Could you start with an existing community? I don't know if it's an online fan forum or a Christian singles site -- but there might be some way to jumpstart your initial user base. (Choose wisely...)

The other obvious idea is promotion. (This obviously works better if you have some capital.) Maybe flood a college campus with incentives and "free trial" offers. Or host a swanky event which can only be attended by people using your dating site.