This is actually a pretty good question, and one that everyone can relate to. I think what really makes a skiddie is the lack of conceptual knowledge. Skiddies, like you mentioned are basically just running tools and seeking a particular outcome. To get to the next level you have to know what those tools you're running are doing. By understanding how and why things work, you can begin to put together your own solutions.
A couple of years ago, I had the same issue. Because security is so damn wide and deep it's hard to know what to focus on. In my experience, you should focus on what you find interesting because it will keep you motivated. Personally, I started a list of everything I thought was interesting about security:
[+] Packet Creation
[+] Network Device Testing / Evasion
[+] Socket Programming (Python, C#)
[+] Remote Vulnerabilities
[+] Archiving Shellcode (accessibility, custom exploit libraries, custom exploits)
[+] Interworkings of DNS
[+] DNS Flaws and Vulns
[+] Python for Pentesters
... and then I just started taking them one by one. It's a lot easier to dedicate a week to one area than to attempt to retain knowledge from a group of them. These are skills you'll want to have solidified so it's important to spend some time with them; enough to really learn the material.
And yes, programming is a big part of not being a skiddie I suppose. I remember reading a great ebook by Scott Whigham called How to Become a C# Programmer (How to Become a Programmer). Given, C# might not be the language you want to learn (it's valuable to know though), however his approach is a damn good guide as to how to improve your programming skills immensely. I know a couple of people that want to become programmers. They talk about "coding" and creating games but they never really get to it. Whigham's approach is a good guideline on how to get started. Basically, you want to think up a pet-project and just get it done. This is the best way to learn.
For example. You want to work on programming that relates to security. So set out to write a port scanner. It doesn't matter what language you do it in.. all that matters is that you complete the project. You'll learn exactly how port scanning works, and you'll eventually complete the project. I'm not saying it'll be easy, but that's the point. Knowledge builds upon knowledge and eventually you'll become comfortable with your language of choice.
Finally, you asked how to get started. Well, I'm a huge fan of the python programming language and I've been using it for practically everything since 1999. It's platform independent, easy to read and dynamic, so you can whip up programs and scripts relatively quickly. Python also has a growing security following. One of the best security related programming books out there is Violent Python by T.J. O'conner. The samples are excellent and you'll learn a lot by tinkering with them. Go pick that book up.
Oh, and keep reading. Read everything. Read whitepapers, books, magazines, press releases, research papers, etc. Basically anything you can get your hands on. It's amazing at how one new idea can change the way you see the world.