Acabo de terminar un proyecto con los mismos componentes (un par de motores dc, Bluetooth, y sensor ultrasónico), sin ningún problema de energía utilizando pilas recargables LiPo de 7.4v en total, por lo que recomiendo su uso.
En caso de que no las conozcas, existen pilas Lipo recargables del mismo tamaño que las AA, pero de 3.7v c/u, con lo que con un par tendrías de sobra para alimentar el Arduino y accesorios (son las LiPo modelo 14500). Ahorras en volumen, peso, y precio (son reutilizables).
También se pueden usar dos o tres Lipo 18650, recicladas de baterías de ordenadores portátiles o nuevas, que también pueden dar cerca de los 3000 mAh cada una; te ahorras el gasto de las baterías desechables y tienes potencia de sobra para cualquier proyecto. El único inconveniente es que necesitarías en cualquier caso un cargador específico, aunque sirven los que se usan para Radio Control.