Although android embed this option natively since a long time, I couldn't use it on this old phone (despite android version being gingerbread), for a reason I still ignore. This would have greatly simplified the task.
So I had to try another solution which was used on very first android version prior to usb tethering native support.
Fortunately arch wiki came at rescue, https://wiki.archlinux.org/index.php/Android_tethering#USB_tethering_with_AziLink
It requires a bit of setup but finally I could make it work.
Not everything is perfect as there are still some issues with DNS notably but the essential is here.
You may not have to do the same thing if your phone automatically support usb tethering, but otherwise you'll need to install azilink on your phone, adb tools + openvpn on arch linux ..., and do some basic setup to make it work... (described on arch wiki and AziLink docs)
Another goal of this first step, was being able to ssh through cubieboard without any ethernet cable (meaning not using local network) but only through internet.
This wasn't trivial, as the cubieboard is hidden behind phone network and ssh server cannot be reached directly as you would with a normal internet connection. So a reverse tunnel must be put in place to do so. I'll try to write build step with more in depth explanation but the idea is to make the cubieboard automatically initiate an ssh connection to the computer that you want to use to reach cubieboard.
This implies cubieboard has to do it itself because it is on its own, through a service which always watch if tunnel is active and relaunch it in case of failure (check the github project where I'll upload important files).