Let's break this down.
According to the Apache 2.0 license, I have to include NOTICE file if it was in the original work. The problem is, that the notice file in the original work was probably never updated and is possibly incorrect as it does not include notices about library dependencies. Do I have to fix this myself or is it enough to just add the dependencies that were introduced by my changes?
You do not need to continue to carry a NOTICE file. Section 4d allows you to include the attribution notices in a NOTICE file, within the source or documentation if it is provided alongside the derivative work, or within a display generated by the derivative work. Specifically, the last sentence of 4d allows you to add your own attribution text alongside (by modifying the NOTICE file) or as an addendum to the NOTICE text (putting both in the same file, within another document, or in a display generated by the derivative work).
Since you're stating that the original NOTICE file is wrong, I would consider doing an addendum by either adding a second NOTICE file that is fully correct, by using one file and calling out which was the NOTICE from the original project and which content is related to your derivative work, or in a display and calling out which was the original NOTICE text and which was your NOTICE text. Regardless - make sure that your NOTICE text is fully correct and don't modify the original project's NOTICE text at all.
The license also requires that I state changes. The original work did not have any CHANGELOG file and changes were tracked in git (which I guess is not sufficient for the needs of the license). How and in what detail do I state the changes in this situation?
A CHANGELOG is not required by Apache. The only mention of requirements related to changes is in 4b, which states that if you modify a file, that file must carry a prominent notice that the file has been changed. Typically, in a project that is using the Apache License (at least those released by the Apache Software Foundation), the top of each file will contain the boilerplate header. The method used to state that a file was changed is to add a new copyright line under the original one. If you are applying a new license to the changes, you would indicate this in the boilerplate header section as well.
Assuming that the initial commit to your git repository was the original work and every revision was your contribution to a derivative work, I think that this is sufficient. You are meeting the requirement of 4b by stating that a file has changed. There is no requirement to further identify changes beyond a file level, but your version control repository would allow for that, if necessary.
Because my work will most likely never be merged back to original project git repository I would like to be stated as one of the authors if possible. I suppose, that I add the mandatory license header to the files that I added to the project, but what about the changes in the files that I only modified? Should I add myself to the NOTICE file? I am not sure how would this look like so any example would be appreciated.
When you modify the boilerplate header, you would add your name. If you are keeping the Apache License for your work, you don't need to do anything else. If you are going to apply a different license, then you do need to identify the license for your contributions to mark off what is Apache License and what is under the other license.
The NOTICE file is only used for attribution to other people. For example, if you are including other projects in yours, the NOTICE file or NOTICE text somewhere else, clearly identifies these other projects and the license that they are under. Modifying the NOTICE file to point back to the original project that yours is a derivative work of would also be appropriate.