1) Make it a one-side market. For example you could let guys set up profiles and then buy Facebook ads to advertise those specific guys ("Think Brad is cute? - He's single, click to find out more") to single girls in their areas with similar interest.
2) Leverage off of another userbase. Tastebuds.fm is a good example that leverages off Last.fm's userbase. If I wanted to take this approach I'd make a dating service for users of 23andme's genetic analysis service. Newspapers will literally fall over each other to write about a dating service that uses DNA to match couples.
3) Take the primary feature of your competitors and turn it into a weakness. Most dating websites focus on having x million members. Turn around a build an exclusive dating website ("fed up having to search through hundreds of profiles and getting most of your messages ignored?"). Only have 20-30 members of either gender at a time and only give them access for a limited period (say a couple of weeks). Have a wait-list for people who want to get on. People will want to signup even without knowing how many people of the other gender or on the system.
The dating site would let you create a landing page to promote yourself (You could also do things like A/B testing on it) and buy advertising to promote it on places like Facebook. It's absolutely irrelevant who else is using the site to promote themselves.
Well, however you spin it, it's a traditional dating site but without any women!
The only unique thing about this idea is that it starts by worsening the chicken and egg problem.
Can you tell me why advertising on Facebook for your profile wouldn't work if there already were women on your dating site? Why not just start selling advertising to people who have profiles on OKcupid, eharmony, PoF and other existing dating sites? If it's irrelevant who else is using the site, then how does excluding one side of the marketplace improve my odds to find a partner?
I think this idea could work - or at least it's not as bad as you are making out.
You are thinking too traditionally.
Imagine the site was called "BankersLookingForDates.com". You charge $5000 (or more?) to become a member, then go visit other dating sites to find women who might be good matches for your members, contact them, vet them and arrange the date.
I was also thinking of #3 - keep it very exclusive.. such as limiting it only to people who are serious about marriage. Make it sorta like a marriage catalog service, but less shady. Make it very very expensive. $10000/year or your money back if you don't find a mate. You get 50% of the money back if you get married though thru the site.
OKCupid did something great by making the questionnaires entertaining to fill out. (As opposed to eHarmony's, which are a slog) I know some people that are just on the site because they have fun answering the questions and poking around.
Makes using it a drag, because lots of people never reply to any of their messages, but make it fun still seems like a good place to start.
smartphone/___location-based ... e.g. "these 3 single women are at o'malley's pub. want to meet one?"
solve chicken and egg by giving the women free drinks or food when they get to a place. this helps the dating network AND the bar by attracting more people to both.
