Not to rain on the parade, but you realize that the arduino in this vid does essentially Zero processing right?

Even if you don't do the ECDSA (which even on bare AVR is probably not possible due to memory restrictions) you still need to securely connect to something that does, which means running at least SSL(also probably impossible), and having a net connection etc.

Android is a much better platform, and thanks to the economy of scale if the cell phone market, not prohibitively expensive in an embedded application. You can pick up an unlocked older model unit to root for < $200, and once you have a working prototype, you can have a cell enabled embedded bitcoin module built for the application.