First of all, the method of just using the elapsed time since the last frame should absolutely work just fine in 99% of all cases. If you're having problems, there's probably a bug in your implementation.
That said, this problem is generally referred to as numerical integration. Given a set of system dynamics (rules that define the next state of the system given the current state and a change in time), you have to compute the trajectory of the system over time.
The simplest method of doing this is called Newton-Euler. That method basically boils down to:
position[t + 1] = position[t] + velocity[t] * dt
velocity[t + 1] = velocity[t] + acceleration[t] * dt
It works as long as
dt is sufficiently small. If Newton-Euler doesn't work for you, you generally move straight on to Runge-Kutta 4. RK4 is a little bit more complex. You will have to store not just the previous and next states of the system, but 4 more intermediate points between the previous and next. Essentially, RK4 tries to predit the next state of the system given the previous state and its derivatives. However, it requires you to be able to say what the position, velocity and acceleration of the object will be in the future as well as the present. This is easy in some systems (like orbiting bodies or falling characters), but is nigh-but-impossible when you've got stuff like collisions involved -- but otherwise it will give you nearly perfect results even when your timestep is quite large.