I am not sure if you understand properly mu questions. I am not asking what the Jordan Decomposition is; this is a well known issue described in books. I may not be expert in this area, but I know more or less what it is. I am also not asking how to obtain the Jordan normal matrix form by using a pen and paper. This task may indeed be the most convenient to accomplish by first solving the characteristic equation, and then finding generalised eigenvectors, etc.
I am asking how to devise a computer algorithm that can solve the task symbolically (by which I mean playing with symbols, not concrete numbers, even not exact numbers such as rational numbers). There is a question how to represent the symbols and operations on them in a computer, and what should be the operations to arrive at the Jordan normal form in the simplest possible way, in cases when such a symbolic solution is feasible (it will not be feasible, if closed form expresisons for the eignvalues don't exist).