Don't want to hijack this thread too much into exercise since its about diet, but honestly, if you want healthy living, good diet and good exercise are inextricably intertwined. So...warning, this post contains a lot of stuff on exercise!
Increasing your base metabolic rate isn't terribly difficult. Sure, genetics plays a part (as always) but its not something you can't work around.
First, you need to shift from three meals a day to six or seven meals a day (keep the overall caloric intake the same). This prevents your body from going into its "must conserve all energy and store it as fat" mode. The goal is to eat healthy and eat balanced. As long as you get enough fiber, potassium, vitamins, minerals, and all that other good stuff, you're on the right track. The other key aspect, as far as weight loss in concerned anyways, is to keep your daily caloric consumption *below* the amount of calories your body burns in a day.
Then you need to do some form of cardio activity that boosts your metabolism. The best type of exercise for this is one that causes your body to go into greater excess post-exercise oxygen consumption (EPOC). Basically, the exercise creates a metabolic imbalance and the body must expend energy to bring itself back to homeostasis. Now, it's not necessarily the EPOC itself that burns all the calories (I think it tends to average around 50-80 extra calories burned over the course of 5-8 hours). Rather, its more likely that exercise that causes a greater EPOC also causes the body to become more efficient at burning fat through more effective enzyme use. Also, greater EPOC activities are also more likely to develop more muscle mass, and as should be common knowledge, more muscle mass means an improved metabolic rate.
The best high EPOC activity is high intensity interval training, and can be performed in different ways (i.e. running, swimming, biking, rowing, jumping rope). After a warp up period, you begin the intervals. For 10-30 seconds (based on your overall athletic ability) you want to perform the activity as fast and as hard as possible (roughly 105% of your VO2 max or 95-100% of your maximum heart rate). Following the intense phase, you go into a short recovery phase lasting 30-50 seconds (the higher your overall athletic ability, the shorter the phase should be). During the recovery phase, you should still be exercising at a moderate speed (65-75% of your VO2 max or 70-75% of your maximum heart rate) so your body isn't at a complete rest or a true cool-down recovery (Which is closer to 50% VO2 max and 50% max heart rate). One intensity phase and one recovery phase equal one interval. The number of intervals you do will base based on your overall athletic ability. Beginners should start at 2-3 intervals and work up to 10-15 intervals over the course of two months or so.
Now, this isn't to say that long-slow distance (LSD) training is bad. Training in LSD is THE most important and effective method for increasing endurance and improving the body's ability to store carbohydrates as fuel. The problem is that most ordinary people really don't need those benefits. You'll only need exceptional endurance if you plan on racing in a long distance event. LSD also will break down muscle that isn't needed, which can be good or bad depending on your needs (good if you're training for a long distance race, bad if you're a body builder trying to add as much muscle as possible).
Finally, it's good to add some form of resistance training to your daily activities. It doesn't need to be anything as intense as power-lifting or ultimately worthless such as body building. As long as the exercise causes some muscle growth, it should be fine. Exercises that improve tone and muscle definition are adequate. Triatheletes generally only do enough weight training to coordinate and improve muscle balance, for example, and they're among the healthiest and fittest people alive.
