This is a sound idea and a good direction to go. Can the arduino perform the crypto functions? There would also ideally be a way to back up the private keys and/or accept imports of private keys for users who know what they're doing.
An arduino, as a turing machine, should be able to perform the crypto functions. Your question does lead to this one though: "Can the arduino perform the crypto functions
in a reasonable amount of time?" On that, I don't have an answer.
I'm not sure about the specifics of the bitcoin public/private key address generation. So someone with more knowledge of the Bitcoin implementation would be required here. I could also look through the source when I have more free time and report back when I find out. I've spent some time looking for documentation and I couldn't find anything about the public/private key address algorithm (not to be confused with the hash confirmation algorithm, which is based on elliptic curve cryptography).