Regarding Nigel's suggestions with the diodes: Put the anode of one diode to the output of your 7805 and the anode of your other diode to the output of your battery. Schottkys work best as they have a lower voltage drop. Then short the 2 cathodes together. When you wall cube is connected (as long as the output voltage of your 7805 is higher than that of the batteries) its diode conducts (and reverse biasses the battery diode). When your wall cube is disconnected, the battery diode conducts. Regarding the battery diode, you might want to make this up of 2 series diodes to stop any reverse leakage current (that might be present in a single diode) charging your batteries.
Alternatively, use the wall cube to drive a relay that disconnects the battery voltage. If you did this, you might still want to add a series resistor coming from the battery just in case your 7805 voltage is much higher than your battery. When you disconnect the wall cube (and hence reconnect the battery), any capacitance across the load will dump itself on the battery. if the voltage is higher, it might try to charge the battery...