1. Don't worry about regulation to the motors; yes, they are 12 volt, but if they "see" a couple volts higher (possible with a fully charged 12 volt battery), it won't likely hurt them. You will probably need regulation to the motor controller logic, but the supply for the motors themselves won't need it (provided that the motor controller can work with greater than 12 volts for the motors, of course - most can).
2. For the microcontroller, servos, and other parts, try to find switching regulators that will fill the need; I know of "drop-in" replacement switching regs for the 7805 - whether those are available for the other 78xx family I am not sure, but I suspect it possible. Note that these regulators aren't as cheap as the linear devices they replace.For the regulators, amperage capability might be an issue. You might be better off trying to find a DC-to-DC converter/regulator module/board that can supply multiple rails at different voltages at several amps each. Such a module, if it can be found, likely won't be inexpensive either.
Alternatively, if you don't mind wasting a lot of power as heat (depending on your current needs, voltage drops, and cooling capability), you could build your own module using linear regulators. Start with one or more 7812 regulators (for multiple 12 volt rails), using "bypass transistors" to gain you more current (this is covered in the datasheet, and in various online sources). Off of the outputs of these rails, add 7809 regulators (perhaps with their own bypass transistors), then from the 7809 rail(s), add 7806/7805 regulators (again, if needed, with bypass transistors). Be sure to add all of the necessary capacitors and such to each and every stage. The idea is to bring the voltages down in stages, with the bypass transistors allowing you more current flow, while spreading out the heat more evenly (be sure to add heatsinks and/or fans for cooling as needed). My only concern with a design like this might be some issue with the regulators not being stable in the configuration, but I have seen similar designs, and people say they do work, so it might be worth trying.Something to keep in mind (read the datasheets) is that while the bypass transistor thing for linear regulators work well for them (provided you use the proper transistor and heatsink as needed), I am not sure that such transistors will work with the switching regulator "drop-ins" - so read their datasheets for more details on how to get more amperage, if you decide to use those instead to roll your own multi-rail switching regulator power supply board.Whatever route you go, be sure to add appropriately sized fuses or breakers before each rail (ie, prior to the 12 volt rails, and in between each "drop" rail) - just a little extra safety precaution.
You also need to size your battery appropriately for the entire load to know the approximate runtime, so it is best to decide on what all the accessories and such will be, what their current needs will be, etc; if there are still unknown accessories, then add some percentage to cover them (or realise that your runtime will be less).