1) Start a mod team for a game such as Half Life, Unreal, Call of Duty, Crysis, Fallout, etc. Keep the scope of your mod small (one single awesome playable level) and add one unique, compelling gameplay feature to the game. When you have that finished, polish it for months, work on the audio, the visuals, everything. Create the most awesome section of game for whatever modding platform you have chosen and then use that as your demo reel. You'll get interviews if you execute well and the rest is up to you and your interviewing skills. (This route has the con that you are not making connections inside of the industry while you are working on your reel).
2) Get a job doing QA for a studio and in your spare time learn the tech that the studio uses and create the exact same thing I described above in your spare time. Do a competent job as a QA guy at the same time. Use your creations as your internal job application. This approach probably has a higher success rate, but it chains your ability to advance to the studio you work in some regards (ie you might not ever be able to show what you make to anyone outside the studio, limiting your portfolio's utility unless you go make something with some publicly accessible tools).
Basically, make an awesome level for a game and you will get a job unless you are scum (and if your level is awesome enough you can probably get away with being scum too -- I'm sort of scummy sometimes and I have a job).