Inside Higher Ed has a really interesting article, Rethinking Science Education, about how some universities are trying to break the mold of the traditional intro-to-a-science course. From the article:
Too many college students are introduced to science through survey courses that consist of facts “often taught as a laundry list and from a historical perspective without much effort to explain their relevance to modern problems.” Only science students with “the persistence of Sisyphus and the patience of Job” will reach the point where they can engage in the kind of science that excited them in the first place, she said.
This is exactly how Intro to Psych is taught pretty much everywhere — as a laundry list of topics and findings, usually old ones. The scientific method is presented didactically as another topic in the list (usually the first one), rather than being woven into the daily experience of the class.
It’s a problem that’s easy to point out, but hard to solve. You almost couldn’t do it as a single instructor working within a traditional curriculum. Our majors take a 4-course sequence: 2 terms of intro, then statistics, then research methods. You’d essentially need to flip that around — start with a course called “The Process of Scientific Discovery in Psychology” and have students start collecting and analyzing data before they’ve even learned most of the traditional Intro topics. Such an approach is described in the article:
One approach to breaking out of this pattern, she said, is to create seminars in which first-year students dive right into science — without spending years memorizing facts. She described a seminar — “The Role of Asymmetry in Development” — that she led for Princeton freshmen in her pre-presidential days.
She started the seminar by asking students “one of the most fundamental questions in developmental biology: how can you create asymmetry in a fertilized egg or a stem cell so that after a single cell division you have two daughter cells that are different from one another?” Students had to discuss their ideas without consulting texts or other sources. Tilghman said that students can in fact engage in such discussions and that in the process, they learn that they can “invent hypotheses themselves.”
Would this work in psychology? I honestly don’t know. One of the big challenges in learning psychology — which generally isn’t an issue for biology or physics or chemistry — is the curse of prior knowledge. Students come to the class with an entire lifetime’s worth of naive theories about human behavior. Intro students wouldn’t invent hypotheses out of nowhere — they’d almost certainly recapitulate cultural wisdom, introspective projections, stereotypes, etc. Maybe that would be a problem. Or maybe it would be a tremendous benefit — what better way to start off learning psychology than to have some of your preconceptions shattered by data that you’ve collected yourself?
The Hardest Science 
Our department had the same inclination, so we spend the first 3 weeks of intro in a “philosophy of science” module. (The scare quotes are there because we don’t read Popper or actual philosophy of science, we just discuss why psychology is a science and the kinds of claims that we make.) We have our students read and discuss chapters from a great book by Keith Stanovich called How to Think Straight About Psychology. It’s also a required text in our stats/methods sequence. Stanovich addresses pre-existing beliefs as a barrier to thinking of psych as a science. We also discuss probabilistic causality and, relatedly, the limits of testimonial evidence. We don’t have them generate hypotheses right away, for the reasons that you mentioned. But I think we are successful in training students to trust data over anecdotes, to not claim that the presence of multiple causes of behavior somehow makes psych not a science, and to really understand why correlational data don’t allow claims of causality.