You will be far better off using a small battery.
The battery is not for running the Micro over the night, but is there to ensure that in low light in the morning when the Solar Panels voltage rises
sufficiently high to start the ATtiny, there is enough current available to run it.
Solar cells dont have a linear voltage / current relationship.
The voltage with no load rises at a logarithmic rate whilst the current capacity rises at a linear rate for a given illumination.
What happens with no battery, is that the solar voltage will rise quickly to above 5 V , which will cause the 7805 to start operating, but the solar cell has no capacity to deliver any current , so the voltage immediately collapses, and the Micro stops.