It sounds like you have already ruled out just diode ORing them together.
I have a project which gets its power from a car battery or a 12V wall wart. What I'd like to do is have both of these wired in, but when the mains power is present, have the battery no longer supplying. The battery and the mains supply are going to be kept independent, so no charging occurs, and I'd like to make it automatic so the battery can kick in almost as a UPS.
How are you going to charge the battery?