Как прошить arduino через GPRS?

На счет GSM не подскажу, но с bluetooth вполне можно (правда там проблемы с перезапуском, приходится рестартовать вручную или костыль в коде лепить). Можно начать например отсюда или отсюда.

https://github.com/Libelium/waspmoteapi/blob/maste...

Там ищите функцию requestOTA. OTA - это акроним "On The Air", обновление "по воздуху".
В ней реализована закачка на MicroSD с FTP новой прошивки.

А уже само обновление прошивки - это обнаружение при старте новой прошивки на флешке и запись ее во флеш микроконтроллера.

Теоретически почему бы и нет. Но представьте что при перепрошивке пропала связь. Передавать по воздуху надо в какую-то память, а уже из памяти прошивать