I stumbled on this by searching through Fou's recent posts looking for a topic about uploaded image protection.. hope you don't mind me dragging it back up!
I wouldn't class myself as a natural programmer yet I've not had anyone teach me either so I thought I'd chime in and contribute my thoughts.
I started with (this'll make you shudder Fou) Delphi (although I tried quick basic years before that and never got to grips with it). Thats Object Orientated Pascal to those who don't know it. Back in the day it was still a fairly popular language and despite being pretty dead now Embacadero (or whatever their name is) are now trying to revive it.
It's not the greatest of languages but it is pretty solid and comes with support for many databases (except mysql naturally) and builds robust .exe programs. It also debugs the actual .exe rather than simulated programs like early versions of VB etc. It's a complex language but I learned a lot from it including how to use threads, sockets etc all of which made life a lot easier when I decided to learn PHP a few years ago.
Switching from a event driven language like Delphi to a non event driven language like PHP was quite a shock though. There are some huge differences and the two technologies work completely differently. With Delphi (or any windows programming languge) you have an IDE, form designer, debugger, windows components (drop down boxes, text boxes etc) at your disposal. With PHP you need to master html, preferably css, maybe javascript and it helps if you can design a good looking page. Then you also have to learn about databases. Now admittedly in delphi I'd never needed this as my projects were not database related and settings were stored inside ini files but it must be said, when I finally figured out how to use a database and link everything in a relational way it made life a lot easier.
I guess what I'm trying to say is that you don't need to be a sheer genius but you do have to have some determination. I've had times when I've bashed holy hell out of my keyboard (I get through one or two a year) but I've stuck with it. The key thing though is that once you've learned one language, it does help you when you want to learn another because you start to figure out the key parts of what you need to understand, how things work, what the language is doing internally etc. Once you've got the basic logic clear in your head it makes life a lot easier. Switching from a complex devil like Delphi to php was a shock but once I mastered the basics it made life a lot easier for me for things like headers - I already understood these as I'd written programs in delphi that used sockets and http protocols etc (hence all the handy tips in my sig where I try to break stuff down for others to understand in plain english).
Fou-Lu is one of the lucky ones who has managed to master almost anything quickly whereas the rest of us can take a bit longer. That shouldn't put you off though, as long as you keep things simple and make sure you fully understand them in your head it all becomes a lot easier as time goes by. Function manuals and knowing how to understand them is also a key element. I've known some people say they can't program because they can't remember functions and their parameters. Neither can I so I had to become inventive. I have a button on my browser that opens a input box - I type in the function name and it takes me to that page on the php manuals website

Cheesy but it works for me very well. If thats any use to anyone else, create a new bookmark / toolbar button and for the url:
Code:
javascript:word=prompt('What%20function%20do%20you%20want%20to%20lookup?',%20'');if(word!=null){URL='http://www.php.net/'+word;location.href=URL;}else{void('');}
Also I can't say enough about formatting your code neatly. Years ago when I first got into programming I didn't care about it - I just wanted to make a program that worked and served a purpose. Fixing its bugs became a nightmare. Opening and closing parts of each block of code were not indented, things were all over the place, I didn't write many functions so had bits of code repeated all over the place.. it was a real mess

Writing neat code and breaking it up into functions makes life a lot easier.
Finally, picking a language which suits your needs is vital. I picked delphi as at the time it had good reviews and it had support for sockets for making programs that could communicate over the internet - something which I needed. Unfortunately what I didn't know was that it would be useless for creating device drivers (eg for usb devices), or running on a mobile device with a MIPS processor which other languages can handle with relative ease. That said, languages like c# rely on .NET being installed on the end users system so whereas that might make life easy in some aspects you then get into trouble if the end user doesn't have the required dependencies installed. Thats where something like the C range might be better suited. Java is the in-thing these days but again you have to be sure that the machine you're code will be running on has java installed. What I'm saying is that you have to choose your language suitably for the task you need it for. Do your research, what do you want to code? - Will that language support it and run in that environment?
The short answer to your question is YES, programming can be done but at different speeds. If you want to write the words greatest program within the next 6 weeks and make yourself rich.. good luck. If however you want to learn to program to create a tool for your business or even as a hobby then time is on your side. Just decide what you want to do and pick a suitable language to start with. Ask around on various forums "Hey guys, will this language be suitable for x, y, z?".
Hope that helps