In classical physics, by knowing the present, can we always uniquely construct the past? In classical mechanics, by knowing the present, is it always possible to uniquely reconstruct the past? By knowing the phase space point at present i.e., the set of coordinates $\{q_i(0),p_i(0)\}$, for all $i$, is it possible to tell which point the system came from?
If not, then I would like to see why, how maybe with a simple example.
 A: 
by knowing the present, is it always possible to uniquely reconstruct the past?

Yes. This is a consequence of Liouville's theorem. According to Liouville's theorem the "volume" in phase space is constant as the system evolves. So if you start with a single point in phase space at one moment in time then at any other moment in time the phase space will also be a single point. It doesn't matter if you trace the phase space evolution forwards or backwards.
This theorem is based on a Hamiltonian with a conserved energy, so it applies at a fundamental level, but may not apply if you are neglecting microscopic degrees of freedom. So “knowing the present” means exact knowledge of the present state including all microscopic degrees of freedom.
Of course, in practice you never know the present exactly. So in reality our practical ability to "predict" the past degrades as we get further away just the same as our ability to predict the future.
A: There are surely many aspects to this question. In particular, the inverse problems are often ill-posed problems. For example, when you reverse time in the heat equation, you have an ill-posed problem because it is extraordinarily sensitive to initial conditions.
See for exemple well-posed problem

Problems that are not well-posed in the sense of Hadamard are termed
ill-posed. Inverse problems are often ill-posed. For example, the
inverse heat equation, deducing a previous distribution of temperature
from final data, is not well-posed in that the solution is highly
sensitive to changes in the final data.

For the damped harmonic oscillator, the time reversal leads to an unstable equation (dissipative force are not reversible) which is also very sensitive to the initial conditions. For example, if you start from rest  (0,0) the solution x(t) = 0 but if you start from $(ε, 0)$ the solution will be exponentially divergent.
A: The question has to do with how irreversibility emerges from the reversible fundamental laws. The laws of motion are reversible in both classical and quantum mechanics, so the question is not specific to the classical case - even though one could argue that in quantum mechanics the irreversibility is introduced via the measurement.
The origins of irreversible behavior lie in thermodynamics/statistical physics, and express themselves as the law of the increase of entropy, which is actually the manifestation of our lack of knowledge about the details of the system. Had we been able to reverse the velocity of all the atoms, the system would evolve back to its initial state (Loschmidt's paradox)If this never happens, it is because such a level of knowledge and control is impossible.
See this question for more discussions.
Remark: Entropy can be defined in different ways and correspondingly mean different things. Here I mean the increase of the uncertainty of the microscopic state that we are in, as expressed by the Boltzmann formula:
$$S=k\log\Omega$$
A: No, because of Chaos Theory.
No, there are systems that are impossible to predict in detail, because even small changes in initial state result in large changes in outcome. These chaotic systems can be as simple as a pair of rod pendulums connected to each other.

Image from Wikipedia
Of course, this is before you even begin to take into account non-deterministic behavior of quantum mechanics, Heisenberg's Uncertainty Principle, or the possibility of a cosmic ray causing a bit to flip in a computer you're modelling the behavior of...
