It all depends on the kind of work you are looking for.
Most companies aren't going to hire your every day average teenager, even one who can demonstrate that they may or may not know whats required for the position,(No offense).
Most of the companies are looking for (like you said) someone with certificates, so you are correct in assuming you can't lie your way through it.
In regards to your main question "How can I, as a 16 year old, get programming-related work?" there are a couple avenues you can take.
The first being exactly as you said, hit the pavement, and hand out resumes detailing what your strengths and weaknesses are, what languages you are proficient in etc... You never know what might come up, I know for a fact you wont get a job if you don't go actively looking for one. The IT industry is very large, but more and more people are becoming much more Savvy, so anything out of the norm you are decent at could be a large help.
The second avenue I would suggest, speaking from personal experience, is app development. I get around 5-6 calls a week asking if my business does app development (Both local and international) everyone is tied to their smartphones, from checking e-mails, to becoming an aspiring Pokemon trainer, the fact is, smartphones are now a heavy part of every day life. Companies are doing their best to market things to the younger generations, which includes app development. It's a pretty large market, and quite a few colleagues of mine have profited quite nicely from app development.
In regards to your "Bonus Question"
If I was a recruiter, short of you being some programming god, I wouldn't even look at someone without certifications. I know it sounds like a A-hole of a thing, but, in my situation at least, I have quite a few large clients, that work very closely with my employees, and it's always an easier sell if you can say "Oh, well John here has 8 certificates, 2 jackrabbits, and a small pony" as opposed to "Here's Bob, he's 16, and he's got a bitchin' haircut"
To sum it up, don't loose faith, and keep your feet on the pavement, eventually something will come up, whether is be coding for a small "mom and pop" operation, or something larger, word spreads quickly if you're good at what you do.
That's just my 2 cents.