Assuming that the diagram you have added is your desired configuration, the answer is yes.
You would install SharePoint on your new server and add it to the existing farm by running the configuration wizard.
For redundancy you would most likely host Central Administration on both servers.
The complexity of setting up NLB really depends on how many Web applications you have.
As James has said there will most likely be downtime while you set this up as you will need to set up clustered IP addresses.
As far as service app redundancy is concerned most services include a form of "load balancing" out of the box, assuming you configure and enable the appropriate services on each box. There are a few service applications (such as the UPS and Search) that suffer from having single points of failure, but generally speaking your farm will still be available should one server go down (the DB server being an exception, as you state).
I suggest trying this out in a test environment before you implement it on production.
It's also worth noting that servers hosting service applications and serving user requests will be under a fair bit of stress so I suggest load testing using a tool such as Visual Studio against your required concurrent usage goals (a rough ball park target would be 10% of your user base).