From there, we cold called / emailed like maniacs - 'here is what we are working on, here is the problem it will solve, here is why you need it, can we have 20-minutes of time to walk you through this?' We leveraged every possible network connection that we had.
When we got people on the phone, we actually showed them mocks of what their site would look like with our platform (lots of Photoshop). Explained that about how we wanted to get them in a beta program, and how much would they pay?
It was a ton of hustle, but we had 10-customers when we launched that were generating a little bit of revenue and willing to give us quotes in the press or get on stage at events.
It is more of a larger, enterprise sale, so it won't work for all companies, but we were essentially selling something that we were building in parallel and wouldn't accept free for an answer.