All of modern psychology is scientific. People who say that it is not, haven't studied psychology or have a media-influenced view of it. Take a course in experimental/cognitive psychology studying all those experiments and models on perception, attention, memory, language recognition and production, categorization, reasoning, problem-solving, decision-making, cognition-emotion interactions etc. informed by computational/neural-network models and see how scientific it is(e.g, Tversky and Kahneman have won the nobel-prize for economics for their pioneering cog. psych experimental research on decision-making).
Psychology gave-rise to "cognitive neuroscience" e.g. investigating cognitive functions by using cog. psychology's tasks and methods (e.g. digit span, go/no-go tasks, object/face-recognition etc.) while subjects undergo functional imaging, cognitive-evoked potentials using EEG etc. Then you have physiological psychology (synomymous with modern behavioural neuroscience) and the possibility of conducting invasive research with animals (e.g. after stereotactic surgery or single-cell recordings), investigating e.g. synaptic plasticity and learning or emotional-autonomic processes. Even the more "social/developmental" aspects of psychology are experimental. Search Milgram's famous experiments on obedience to authority, Asch's on social conformity and a lot of exciting modern experimental research on social cognition (which IMO has significant mental-health applications, e.g. how we attribute causality and its' relation to depressive and psychotic states). Also a lot of crucial experimental research on kids e.g. on how they learn and organize their perceptions or linquistic concepts.
Psychology is as scientific as it can be. It is the ideal subject if you want to think about the structure and function of abstract functions by conducting empirical research. I have also taken biochem and physiology courses and while biochemistry can be more daunting, e.g. in memorizing every little thing of a metabolic pathway, cognitive psychology (e.g. how human deductive and inductive reasoning works, how concepts are organized in semantic memory, or how we recognize objects and people) can demand a much more analytical-type of thinking. I personally think it as very similar to physiology (with the ways of thinking and the type of reasoning for conducting experiments) with the main difference being that in physiology you get much more straightforward linear models (e.g. cardio-vascular dynamics) whereas in experimental psychology you get more non-linear multifactorial functions (e.g. factors thay affect memory-recall and memory-recognition)
Have a look at the journals of experimental psychology (like "human perception and performance" or "learning, memory and cognition")
So, just major in whatever you like but obvious combos (as others have suggested) are major neuroscience/physiology, minor psychology or the opposite (although the first one would probably be easier for med-school). There is overlap in many ways (common courses)
