I am currently working for what could be considered a startup based in the UK (I am in the US). It's a fairly interesting problem, but not normal "startupish" stuff.
I have no formal education, no credentials (other than code).
I landed this job by doing what I had been doing for a while: going to the bottom-of-the-barrel freelance sites like rentacoder, and skimming through the job postings each day until I found things that didn't look painfully boring, weren't asking for way too much for way too little, and weren't "OMG FIX MY PHP CODEBASE" - because I had done a few of those, and they are far from fun. That's another story though.
I did (and still do) have an ace up my sleeve - I live really cheaply. This meant that I could grab up the interesting projects that got put there because the company doing the interesting stuff overloaded one guy, or because they couldn't afford a "consultant", do them for cheap, and do them well - which gained me repeat customers.
My current employment happened when after finishing one project, the client asked me to do another, very similar project. I inquired about what he was doing, and it turned out that he was doing a bunch of these really similar projects, that would be better implemented as one kinda loose project.
Wheee.
I guess I don't have much experience with the actual "job market" - but I can say that if you're a person like me, the jobs are there. You just have to be willing to work for cheap, at least for a bit (I'm not even close to rolling in the dough, but I have enough to pay my rent and bills and save some money for trying to attend college next year).
With the bottom-of-the-barrel freelance sites, just communicating well and not being a bot puts you in the top 95% of bidders for a job. It's really that ridiculous. If you don't have much official prior experience, you'll probably have to do some real crap work real cheap - but once you've got a few "this guy is good" bits of feedback, you pretty much have your pick of the lot.