Got a super low paid almost intern-type job at a very respected institution. Once that was on my resume, people didn't care (and I sure didn't go out of my way to tell them... I would if they asked, but they never asked) how low level the job was... they just saw the respected institution name and I was golden for the next step.

Also had published some software that got me the first couple jobs. Publishing some software (open source, or an app in an app store) is a great way to get the credibility you need.

If these are not an option, you could work for a friend, long enough to get something you can point to as yours.