After four months, I had become the longest tenured employee (besides the owner, who was non-technical) after everyone else in the company quit. I had no choice but to take the role of Lead Developer on a $170,000 project. Needless to say, I learned to code ... and since then my interest in CS/SWE has snowballed to the point I enrolled in a M.S. Comp Sci program.
I did tech support with them for a week and ended up taking on a web site project as well. A couple weeks later came another project... and another... and then then two years later we had a good laugh when we realized that they never hired me officially.
My first real programming gig came out of the blue as well. I had just graduated high school in North Carolina and received an e-mail from a startup in California. They had learned about me from my work on Gaim (now Pidgin) and wanted to hire me.
Two weeks later I was driving across the country to start the job. I don't even think there was an interview involved. I almost half expected to get there and find an abandoned building.
That was many years ago. Sadly, I now find myself somewhat underemployed and toying around with a few startup ideas while longing to move back to California.
I got my first real job through Monster.com, I'm sorry to say. I had just moved to a new town and a company needed some help, so I went ahead and applied. It wasn't a great gig, but I wasn't trying to be selective at the time. I would not recommend using Monster.com and if I could go back in time to slap myself I would. I still get occasional calls from recruiters for a 4-year old resume.
The best advice I can offer you is that, however you brand yourself on your resume, tell the truth in an interview. Don't exaggerate or fabricate, and if you get to the limits of your knowledge don't be afraid to say so. Think of it as an extension of "underpromise and overdeliver". I never put anything on my resume I'm not prepared to talk about for at least half an hour precisely to avoid any hint that I'm making shit up as I go.
I did that, which was fantastic experience (good coworkers, nice codebase to work with and an interesting industry) and led to me being employed by the same company upon leaving University. While interviewing for my next job, it was often mentioned that I had 18 months more experience than others in my position (recent-ish graduate), and they valued that much more highly than they would one additional year of in-University education.
As for getting a job without a educational backing, it's all about proving yourself. I have a friend who's co-worker had never been formally educated, but was a senior developer at the firm. He had a solid portfolio and ran his own small web development effort on the side. Code things, and show them to prospective employers.
I recommend identifying what you want to do, find out who's doing it, and then contacting people there directly until they bring you in. Knowing what I know now, my approach of mostly sending out resumes and hoping for the best was not optimal. I still don't know how to "network" but calling companies that are doing cool things, or asking people on irc where they work and whether they like it, things like that, are probably going to be sort of like networking.
Networks and job fairs are fairly useful. If you attend conferences or talks, get to know the people there.
He asked me if I wanted to take over the template building process for them, and I agreed. Started as a contractor and ended up working there full time for almost three years straight out of high school.
If I were you, I'd try contacting companies that are doing things to want to do and sending them your resume. Persistence is key.