Indeed, I could win some bytes by passing only the changes between data points but I won't be able to divide the number by 3.
Bluetooth is the best choice to do a wireless low-energy connection with an Android device.
It is impossible to have idle time, or wait to send because I must receive the data in "real-time" and the movement speed is constant.
Following your ideas, I found this SPI to UART converter : https://www.sparkfun.com/products/9981
With it, I should be able to run my Bluetooth module at full speed (460800 bauds) so my problem will be solved, given that the time taken by the functions of Arduino's SPI to transmit to the converter the message to be converted to Serial is small enough...