"How many times do we ever face situations where we sit down to do things that are totally new to us?"
The vast majority of my day, and the vast majority of my career. If you're not, it's most likely because you're not challenging yourself, and you've got nobody to blame for that but yourself.
When I first got out into the working world, I read all the posts that said "Really, the vast majority of programming is just plugging together pre-wired components and pulling stuff out of a database to stick on the screen, and all the interesting problems have been solved already." I thought that sounded terribly depressing, but I liked programming and it paid well, so I figured I'd deal with it later. And sure enough, after spending 3 years in college working on a PHP webapp and about a year at my first job wrestling with JSF/Hibernate, I was pretty bored.
That's not even counting backend stuff. After a year and a half as a FE SWE in Search, I was starting to get pretty bored, so I asked to do backend stuff. I ended up working on an LLVM-based JIT for a templating language; the spec for Google's Authorship markup; the implementation of said markup throughout the indexing & serving system; a bunch of unstructured data-extraction tasks; and most recently some machine-learning with libsvm. All of these were new, and all were challenging.
And that's not even including soft skills like code reviews, mentoring, interviewing, managing up, product & UX design, and project planning. Having 3000 lines of code dumped on you on Wednesday when they want to get it in by Friday, needing to quickly figure out how it all works, and knowing that if you screw up you'll break google.com is something entirely different from hitting autocomplete in your IDE.
I'm beginning to think that if you know exactly what to do, you probably have no clue what you're doing. Real engineering is all about trade-offs: it's knowing that if you implement this new feature, it'll cost you a millisecond in latency and 2 months of engineer time, it'll have some unspecified effect on future productivity, and it may result in X number of happy users. And then you have to weigh those unknowns and decide "Given what I know, is this how we should do it?" If you know the answer to that immediately, your product is probably lame, because it means you didn't even consider alternatives.
I've heard that argument before. I don't think I did anything that other people cannot do.
My overall point is that if you start believing that programming is just rote work that takes no skill, it becomes a self-fulfilling prophecy. Because then you never take on the challenges that will get you skills, and you're unqualified for jobs that will bring you more challenges, and eventually you end up falling so far behind that it seems hopeless. It really has very little to do with ability and a lot to do with constantly looking for ways that you can make the user experience a bit better at the expense of making things a little harder for yourself.