Get rid of the output capacitor. That circuit was probably meant to produce a signal around zero, so the capacitor is there to block the 1/2 Vdd offset. However, the microcontroller wants to see the signal centered around 1/2 Vdd, so just get rid of the capacitor.
Microcphones do need a lot of gain. Electrets can be sensitive, but you still might need a voltage gain of 1000. The gain in your circuit is the ratio of R5 to R2, but this only works within limits of what the opamp can do.
The values you mentioned above would give you a gain of 5000. That's a lot more than you should try to get from a single opamp stage. Not only will the offset voltage be multiplied by this gain, but the opamp won't be able to provide that over the full frequency range. At 1 MHz gain-bandwidth, you'll only get that gain somewhat below 200 Hz. Even a 1 mV input offset becomes 5 V after amplification by 5000.
R2 is also the impedance seen by the microphone after the input capacitor. You need this to be somewhat larger than the impedance of the microphone with its pullup and the input capacitor at the lowest frequency of interest. 10 Ω is way too small for that. 10 kΩ would be a better value.
Try two stages with a gain of 30 or so for starters and see where that gets you. That's a gain it can handle over reasonable frequencies with enough headroom left for the feedback to work. You also need to capacitively couple the two stages so that the input offset voltage does not accumulate thru all the stages.
Edit: Added circuit
I didn't have time to draw a circuit last night when I wrote the reply above. Here is a circuit that should do it:
This has a voltage gain of roughly 1000, which should be sufficient for a reasonable electret microphone. I may be a little too much, but its easy to add some attenuation.
The topology is rather different from your circuit. The most important single thing to note is that it doesn't try to produce the whole gain in one stage. Each stage has a gain of about 31. That leaves plenty of gain headroom at the maximum audio frequency of 20 kHz for the feedback, so the gain will be nicely predictable and flat accross the audio frequency range since the MCP6022 has a typical gain-bandwidth product of 10 MHz. The limiting factor will most likely be the microphone.
Unlike what I said before, the two stages do not need to be capacitively coupled to prevent the offset voltage accumulating along with the gain. That is because in this circuit, each stage has only a DC gain of 1, so the final offset is only twice the opamp offset. These opamps have only 500 µV offset, so the final offset is only 1 mV due to the opamps. There will be more due to the mismatch of R3 and R4. In any case, the output DC will be plenty close enough to 1/2 the supply to not eat into the A/D range in a meaningful way.
The DC gain of 1 per stage is achieved by capacitively coupling the feedback divider path to ground. The capacitor blocks DC, so each stage is just a unity follower for DC. The full AC gain is realized as the capacitor (C3 in the first stage) impedance gets small compared to the lower divider resistor (R7 in the first stage). This starts to happen at about 16 Hz. One drawback to this approach is that the time constant to settle is C3 times R7+R5, not just R7. This circuit will take a couple of seconds or so to stabalize after being turned on.
Based on the report that it works when the circuit is powered by its own battery, it really sounds like the laptop's USB VBUS supply is noisy when operating off batteries.
Maybe the VBUS comes from a badly implemented switching regulator or DC/DC converter or one with some failed components in it, that is under more stress when operating off batteries than when off the likely higher charger voltage.
It should be possible to filter this supply using both a series inductor and a cap - this will be more effective than a capacitor alone. You can even do multiple stages of such filters.
But it may be easier to just use a battery if that works for you.
Best Answer
I'm almost afraid to tackle this one, but here goes.
Stop. Just stop. Forget EKGs. Get a cheap DMM, find a web page that deals with really simple op amp circuits, and start building really basic stuff, like a voltage follower, then a non-inverting amp with a gain of 2, and work up from there. The LM358 data sheet has some very basic circuits that you can try. At this point there is simply no way help you "fix" what you've done. Your schematic makes no sense at all, and the Fritzing does not correspond to the schematic.
In the schematic, there is no pin connected appropriately. Not one. First, you show an OP37, then you say you don't actually have an OP37, you have an LM358. Why did you do this? You have +5 going to the V- input, and D9 going to the V+. The LM358 doesn't have trim inputs, and on the OP37 that's not how to connect them. And the output doesn't go anywhere. Finally, an op amp is not run "open-loop" - that is, without feedback from the output to at least one of the inputs. So just running your signals directly into the inputs is not going to work. Like I say, there is not a single pin connected appropriately.
The Fritzing shows, for instance, +5 connected to pins 4,5,7 and back to DIN. There is no ground connection to the breadboard, so there is no ground connection to the op amp.
I'm sorry, but when you're this far off, there's no easy place to start.
Cease with the EKG for now. Concentrate on making a few simple circuits that work, and only then move on to something more complicated.