APU removed altogether
On an aircraft such as a 737, the distribution of the pax and baggage/freight quite possibly would need to be non-standard, i.e. more of the load being placed towards the rear of the aircraft. Having said that, balance problems for airliners at least, tend to relate to the centre of gravity being too far to the rear. Assuming the balance problem can be overcome, the overall payload wouldn't be affected.
As has previously been mentioned, although aircraft regularly fly around with the APU inoperative, I would imagine it's very unusual for it fly around with it removed altogether. If the APU needs complete replacement, an aircraft would generally fly around with the duff one still in place until a replacement is fitted.