I asked the computer techies in many of the companies I've worked in as a secretary how they got their jobs, because I was once interested in getting into that field too. I never once heard someone say that they went to school for it. Maybe a class here and there, but they just tend to be people who like to "mess around" with computers. However, that was years ago, and while work in the computer fields is still more about ability and experience than holding a certification or degree, paper proof of your ability has become a way of gaining an edge on the competition.
Still, not all programmers have certifications, and you are an example of why. In 2004, about 20% of programmers had a high school education only.
You could try calling the number on one of the ads in your local newspaper and see if anybody will give a beginner a break. It could be that a smaller company will be glad to try you out because they won't have to shell out so much for you as for a more experienced programmer. Or, find some large company with an entire programming department, and you could pick up what you still need to tighten up on during orientation training; plus, and as they know, you'd continually pick up more knowledge from working with and around the other programmers.
If you decide to go for certification first, you could try either a local college or university's adult education classes, or a completely online certificate program, like Baker Online, which offers just the one you're talking about,
AS In Computer Programming: JAVA Option.
Check it out by going to the first link listed in Sources below,
then choose Baker Online in purple in about the middle of the page,
and finally AS In Computer Programming: JAVA Option, from the drop-down in item 3. Program of Interest.