Do I need to check battery level at all?
Can I damage something on the USB device or battery if I just leave it connected?
You can damage the NI-MH or CD packs by totally discharging them and leaving them in that state for very long. Small nickel crystals form and poke between the separator shorting the cell out. This doesn't happen except when the cell is completely discharged and is the major cause of cell failure.
Use a battery monitor of some kind and remember that it too draws current.
Bob
something using this principle as example
Is there a way to do this without zener diodes?
For me its totally ok to use an ATtiny because I have one here and I would have to order new stuff again and wait for it to be delivered 
However, I just tested the 7805 and it works just as I expected
I connected my cellphone to it and it indicates that its charging, but it only consumes 0.11A and the battery level does not rise. Any idea whats wrong? The schematics says that it can provide 1A (thats also the limit of the cellphone wallwart).
The cellphone will pull however much current it needs. It won't pull 1A just because it can. The charge controller will vary the charging current based on the condition of the battery and whatever algorithm it's programmed with. I don't know if 110mA is considered typical or not.