I'd say there were almost no prerequisites for learning Langrangian and Hamiltonian mechanics.
First thing to say is that there's almost no difference between them. They're both part of the same overarching framework. Basically it's a convenient way to write down general laws of physics. There's nothing too difficult or scary about it, and it's a lot more elegant than Newtonian theory.
If you have a rough grasp of basic physics, I don't think you need to formally learn Newtonian theory first. I had to as an undergraduate and it was a horrible mess. I've never needed to do anything using purely Newtonian theory since.
You might need to know how to solve differential equations, both ordinary and partial, but it's possible to pick this up as you go along. There's almost no linear algebra needed, so don't worry about that.
If you're looking for a book, the best one is Landau and Lifschitz, Volume I. Their exposition is very clear and concise, ideal in a textbook! Good luck!