Using only the phone's (Android) built in accelerometer, how would I go about finding its velocity?
I have been tinkering with the maths of this but whatever function I come up with tends to lead to exponential growth of the velocity. I am working from the assumption that on startup of the App, the phone is at a standstill. This should definitely make finding the velocity (at least roughly) possible.
I have a decent background in physics and math too, so I shouldn't have any difficulty with any concepts here.
How should I do it?
That will really depend on what the acceleration is and for how long. A mild, long acceleration could be measurable, but any sudden increase in acceleration, followed by a constant velocity, will make your measurements quite difficult and prone to error.
Assuming constant acceleration, the formula is extremely simple: a = (V1-V0)/t . So, knowing the time and the acceleration, and assuming V0 = 0, then V1 = a*t
In a more real world, you probably won't have a constant acceleration, so you should calculate Delta V for each measurement, and adding all those changes in velocity to get the final velocity. Always consider that you won't have a continuous acceleration data, so this is the most feasible way (i.e, real data vs integral math theory).
In any way, even in the best scenario, you will end up with a very high error margin, so I do not recommend this approach for any app that truly depends on real velocities.