A wall pack is great if it's not for a mobile/robot platform.
Servos have an initial surge, just as any motor. So, kicking all 4 on at once would be a kick in the shorts.
The more weight, the more work, the more current.
7.2V NiMH rechargeable packs (a pack and a charger) can be found at hobby/RC stores handily.
You should be able to run the servos (6V) safely off the 4-cell pack through a diode.
Try running the rest using a 9V battery, however short-lived, into the 5V regulator to see how things go better.