I wouldn't try to eat more calories to put on muscle, as there's no guarantee it's going to turn to muscle in your upper body. It could turn to fat on your hips, which would make doing pushups even harder. The only way (that I know of anyway) to get stronger is to do lots and lots of weight training. I've been training for about 2.5 years, and I've made great progress since starting. I started slow, and just slowly built myself up to being able to do the minimum physical requirements. Of course, I'm not happy with being able to do just the minimum, so I keep pushing myself to improve. Try lots of different things (within reason!), to mix up your workouts and work your muscles in a more rounded way. I have 3 weight routines that I use (about a half hour each) each week, and on the opposite days I do cardio. Try to do as much full body exercises as you can (squats, pushups, chinups, etc.). Keep a record of what you do every time you workout, and never be satisfied with your current level, always try to do a little more than you could on your last workout (don't hurt yourself though!). Also, do check out stumptuous.com, she's talking about weight lifting and strength training for women, and she does it in a very accessible and funny way. (Of course she's funny, she's Canadian!). She also has lots of information about nutrition, and dispels many myths about weight training, fat loss, etc.
Good luck!