Paradox in Circuit Theory Consider the simple case of a battery in series with a resistor, mediated by conducting wire.

At steady state, the charge carriers are circulating around the circuit at constant speed through the conducting wires. From this we can conclude that the battery is doing no work on the charge carriers (or else the charge carriers would gain kinetic energy), and the entirety of the battery's energy output is being dissipated by the resistor in the form of heat ($V I$ watts).
Edit: It has been pointed out by multiple responses that this point is incorrect. It is more proper to say that work is done on the charge, and then negative work is done on it again inside the resistor. However, I think we can still argue that electric field is 0 inside the conducting wire and continue with the paradox.
Let $E$ be the electric field and $\gamma$ be a path completely contained in the circuit and that begins and ends inside a conducting wire. Since the battery does no work on the charge carriers, it follows that $\text{work} = \int_\gamma E \cdot dl = 0$. In particular, $E \equiv 0$ at all points in the conducting wires.
Edit: To fix the argument here, I should say that the electric field is 0 inside the conducting wire simply because charges do not accelerate at any point within the conducting wire.
Since the circuit has a net neutral charge overall, there is no electric field in the ambient space outside of the circuit.
The only nonzero electric field is contained within the battery and resistor themselves, and their fluctuations are responsible for the net increase in kinetic energy of the particles inside the resistor.
Now add in an uncharged capacitor in parallel with the resistor.

Initially, the total electric field between the plates of the capacitor is the one produced by the circuit in the ambient space, which was found to be zero. And since there are no forces which cause charge carriers to accumulate on one of the plates, the field between the plates will remain zero.
This state of affairs contradicts circuit theory, which predicts an electric field will form between the plates due to an accumulation of charge carriers on one of the plates.
What is the resolution?
 A: Unfortunately, this question straddles the boundaries between circuit theory and electromagnetism. Such questions are rather out of scope for a circuit theory class and disappointingly they are usually not well covered in an electromagnetism course. I will try to bridge both or answer with both theories as much as possible.

At steady state, the charge carriers are circulating around the circuit at constant speed through the conducting wires. From this we can conclude that the battery is doing no work on the charge carriers,

This conclusion is incorrect. From a circuit theory point of view the battery has a non-zero current and voltage and therefore the $P=IV$ is also non-zero (positive). From an electromagnetism point of view the work on charge carriers is given by $\mathbf E \cdot \mathbf J$ which is also positive inside the battery.
The fact that the speed is constant does not imply that the work done by the battery is zero. Similarly, the gears on the pedal of a bicycle do positive work on the chain even though the speed of the chain does not increase. There is simply another source that is doing negative work.

Since the circuit is neutrally charged overall, there is no electric field in the ambient space outside of the circuit.
The only nonzero electric field is contained within the battery and resistor themselves, and their fluctuations are responsible for the net increase in kinetic energy of the particles inside the resistor.

This is not correct. Although the circuit has a neutral net charge that only implies that there is no monopolar field in the ambient space outside the circuit. There may be dipole and higher order multipolar fields present.
In particular, surface charges are extremely important in the normal operation of a circuit. They produce rather complicated fields in the ambient space outside the circuit. Here is a semi-quantitative treatment. See in particular figures 7 and 9 which detail the ambient fields. I like the way that this paper bridges basic electromagnetism and circuit theory.

Initially, the total electric field between the plates of the capacitor is the one produced by the circuit in the ambient space, which was found to be zero. And since there are no forces which cause charge carriers to accumulate on one of the plates, the field between the plates will remain zero.
This state of affairs contradicts circuit theory, which predicts an electric field will form between the plates due to an accumulation of charge carriers on one of the plates.

As shown in the paper above, there is an ambient electric field initially which is caused by the surface charges in the circuit. This electric field drives the accumulation of charge carriers on the plate until the capacitor field balances the ambient field at the connection point and charges are no longer driven towards the plates. (This particular scenario cannot be solved in circuit theory with purely ideal components since it would briefly produce an infinite current through the capacitor)
A: 
From this we can conclude that the battery is doing no work on the charge carriers.

Nope.  The battery is doing work on the charge carriers, which are then doing work on the resistor.  The battery is a voltage source; electrons going through it see an increase in their energy, which is then dissipated as they force their way through the resistor.
So -- no paradox.

Since the circuit has a net neutral charge overall, there is no electric field in the ambient space outside of the circuit.

Nope.  There is a voltage between the wires at the top of the schematic and those at the bottom.  So while the circuit may or may not have a net neutral charge, there will be an electric field from dipole-ish caused by the wires and battery.  Specifically, assuming you make a circuit that mechanically matches the schematic, your capacitor would end up an area of maximal electric field, because it's right between the + and - wires.
So, again, no paradox.
A: 
From this we can conclude that the battery is doing no work on the charge carriers

How does this follow?  The charges on the low side are at a lower potential than the high side.  The voltage source is doing work on the charges to move them to the higher potential.

Since the circuit is neutrally charged overall, there is no electric field in the ambient space outside of the circuit.

That's insufficient.  If you imagine a neutral dipole (like a hydrogen atom or similar), the object has no net charge, but will have a non-zero electric field away from the object that depends on the dipole strength.  The circuit may be neutral overall, but it could have excess charge on one side and therefore a field between.

in every-day circuits, the capacitor in the circuit can be rotated in a way that the charge accumulation opposes whatever ambient field exists, and yet charge will accumulate somehow.

The capacitor is not charged due to the ambient field, but due to the field that arises from the motion of the charges in the connected conductors.  As long as you've connected it to wires, the orientation doesn't matter much because the wires constrain where the charges will flow.  The moving charges will create a field of sufficient strength within the capacitor.    

To fix the argument here, I should say that the electric field is 0 inside the conducting wire simply because charges do not accelerate at any point within the conducting wire.

While there will be an insignificant field in the wire, the argument about no acceleration is insufficient.   That just says that there is no net force on the charge, not that the field is doing no work.
If I descend down a hill in my car at a constant speed, I can't conclude there is no gravitational field since the car is not accelerating.  Instead, we say the gravitational field work is opposed by the brake.  In our circuit, the electric field in the resistor is "pushing" the charges forward at exactly the same rate that the resistance is opposing them.  The end result is a constant speed and constant KE but losing potential.

Since the circuit has a net neutral charge overall, there is no electric field in the ambient space outside of the circuit.

Imagine that the (neutral) wires move charge so that there is an excess between the voltage source and the resistor.  Then there will be a deficit on the other branch of the circuit.  There will then be an electric field between the two branches even though the circuit is still neutral overall.
A: Only because charge carriers are flowing at a constant velocity around a circuit (they always do in DC circuits) doesn't mean there is no field. The battery constantly pumps charge carriers AGAINST the electric field appearing at its poles, by virtue of the electrochemical processes inside it. Thus the battery does work. This energy is completely dissipated when the charge carriers drift down the potential difference on their way through the resistor, where they scatter off mostly lattice defects, creating tons of phonons, i.e. heat.
Regarding the electric field: Only because the whole circuit has net charge 0, doesn't mean there is no electric field outside of the elements themselves. There certainly will be an electric field close to both the battery, and the resistor. Agreed, if you go far enough away from the circuit, it won't have electric monopole or dipole terms, but in the near field, there is still non-zero E field.
A: I only know barebones basics of circuits and electromagnetism. Still I will try to clear your doubts.

Initially, the total electric field between the plates of the capacitor is the one produced by the circuit in the ambient space, which was found to be zero. And since there are no forces which cause charge carriers to accumulate on one of the plates, the field between the plates will remain zero. This state of affairs contradicts circuit theory, which predicts an electric field will form between the plates due to an accumulation of charge carriers on one of the plates.

The field inside a perfect magical conducting wire in steady state will be zero and thus the charges will move with a constant velocity. However you are saying that there are no forces that cause the charge carriers to accumulate on the plates of the capacitor. A force is not required to accumulate charges on the capacitor.
Charges with a constant velocity still constitute a constant current. When the charge carriers encounter a "gap" in the conducting wire in the form of the capacitor plate (we assume the gap has infinite resistance) the charge carriers will lose all of their kinetic energy and stop at the capacitor plate, unable to cross the infinite resistance. The kinetic energy of the charge carriers will get converted into the energy of the electric field between the plates of the capacitor. In steady state the field produced by the capacitor will oppose charge carriers looking to enter the capacitor branch.
So even in an ideal conducting wire of zero resistance and no leaking ambient fields, both of which we frequently assume in circuits, the capacitor will still get charged. 
Of course in real circuits, ideal conducting wires do not exist and there is a field developed in them and there is some ambient field around the wire. But even in the ideal case it works perfectly fine.
