I hadn't thought of a battery like those Yuasa. I can probably get one from a buddy who has a bunch. I just really don't want another car battery sized thing.
I'm not sure I follow the need for the regulator. There is already one built into the Arduino. I'm not up on the dual battery setups and will need to read some but would think you need a relay that would hold open when the computer(or ignition) is on and slam immediately there after to keep from draining the main crank battery. Sounds like you suggest a current limiter to keep from smoking the little guy when it starts charging? I assume it would just charge like normal off of the charging system. I would also guess a GOOD diode is in order.