Why do atheists continually deny they have any belief at all?
Not believing something is really and truly different from positive belief. I like to use the example of unicorns, which most people don't believe in, even though they're not very extravagant as mythical creatures go. After all, they're just horses with horns. They certainly seem possible.
Still, if pressed, most of us would say we don't believe in unicorns. This is different from declaring that unicorns definitely do not exist, which would be a groundless belief. We simply don't believe in them because there isn't any good evidence that they exist, children's coloring books aside.
Perhaps you are referring to atheists who positively declare that there are definitely no gods. I would agree with you that this is a belief because it is a postive statement about the universe, for which there is no evidence. (The only way you could definitively rule out gods would be total knowledge of the universe, which no one has.)
However, there really aren't many atheists who make that kind of claim because atheists tend to be sensitive to logic and see that that would be a faulty position. Even "rabid" atheists such as Dawkins are careful to say when pressed that while they feel very confident that there are no gods, it is not possible to rule them out completely. This is analogous to you or I being "very confident" that unicons do not exist, even though we can't say with 100% certainty.
But that is the nature of knowledge in general. We can be very, very doubtful of the existence of unicorns, but it is always possible that there is a secret underground lair leading to a paradise world in Middle Earth where the unicorns run free. It is possible that the universe was created by a flying spaghetti monster. But in the absense of evidence, we can freely dismiss such claims.
The same is true of the god proposition. Anything is possible, of course, but in the absense of evidence, there is no reason to accept any particular claim. Atheists are a-theists in the same way that they are a-unicornists or a-Elvis-is-still-alive-ists. The only reason there is a name for the position at all is because so many people do believe in gods. Imagine a world filled with unicorn-believers, in which only a minority refrained from belief until such time as evidence might be presented. Do those people have a belief in the same way that the unicorn people have belief?
Isn't believing that everything has a logical natural explanation a belief?
You're right about this one. But this is a fundamental assumption that all of us apply to every single ordinary event in life. When you find a broken dish, you assume that there was a sequence of events leading to its getting broken. We just don't seem to live in a world in which things happen magically, without rhyme or reason, and indeed it is difficult to conceive of such a world even working. But you're right, it is a basic assumption that we must make. So far, the universe seems to support this notion, but we can never know for certain.
Actually, this assumption does not really bear on the question of gods. After all, gods could certainly exist in either kind of universe (that is, rational and irrational universes). It's just that in a universe where 2 + 2 only sometimes equals 4, it would be even harder to know anything at all, let alone whether gods exist.
Anyway, hope that wasn't too rambling of a post.