Is there anything in the universe that is completely static? Based on my current, admittedly deficient, understanding of physics everything in the universe is in constant change and motion. 
Is that understanding correct or is there something that is static?
By static I mean that all of that object's properties remain constant from one moment in time to the next. These properties include its position/motion as well as the properties of its internal structure.
 A: For a massive particle you can always find a frame where it is at rest - its proper frame, and you can always find a frame that is moving relative to that particle (so according to that frame the particle is in motion). A massless particle is always moving and has always the speed of light relative to every inertial frame. In order for the state of motion to be defined, one has to specify the frame relative to which the state of motion is evaluated.
A: For us to talk about "static," we have to be able to talk about a reference frame in which we are measuring something.  As several people have mentioned, it is always possible to construct a reference frame with respect to a particle, and that particle will be static in that frame.
However, if I venture a guess and say that you are talking about a system which is unchanging the current prevailing opinion is that everything changes.  In particular, the first law of thermodynamics says that entropy is always increasing, so there is always energy being converted into heat.
Could there be a system that is truly static?  We actually can't disprove it.  But from what we have seen, all macroscopic systems exhibit thermodynamic behaviors -- they all increase in entropy.
We can theorize about the existence of static systems, especially on the small scale, but to the best of our current understanding, no system actually earns the title of "static."
A: Your question is about absolute state of rest or motion. Unfortunately, at the time we only understand relativistic states and are no where close to understanding absolute state even if there is such a thing.
It is natural to ask this question. But say something is supposed to be absolutely static, how do you prove it is static? You have to be in the same frame of reference as that thing. You can do that anytime with stuff in your surroundings.
If you draw an imaginary spherical shell around you, then you must be moving at a specific speed in specific direction at a given time wrt that shell. Unfortunately we do not have means to figure that out.
A: Completely immune to change
As far as we know so far (which does not say much), the basic rules of our universe are immune to change. I.e., the concrete numbers which make up our fabric. Things like the relationship between the masses, charges, spins of the particles we know about; light speed and so on. But we do have theories which in theory (sic) could change this...
Plenty of static except for very catastrophic events
All atoms are, when viewed individually, static except for catastrophic events.
Take any old lump of rock flying through space, on a benign route through relatively unpopulated areas (which, since space is BIG, is pretty much all rocks, everywhere). Not only rocks, but everything that is not an active sun or a black hole, i.e., planets, moons etc.
Yes, eventually something bad may be happening to that rock as a whole, it may fall into a star and, depending on the nature of the star and the material of the lump-of-rock, become part of some fusion process. But unless you take this case, which in the grand scale of things should be of absurdly low probability, or take at the least an absurdly large amount of time, the individual (non-radioactive) atoms in that lump of rock will never change in the slightest. 
Certainly the body itself will be re-arranged once in a while, i.e. when it hits another rock; and if it should crash into a moon, planet or star they will be pretty severely re-arranged. But other than fusion or black holes there is just no process that will change (non-radioactive) atoms. They will always have the same charge, number of protons, quark buildup etc.; they might lose or gain an electron or neutron here or there but those are part of the "dynamic" scope of atoms anyways, and that's part of life, not a fundamental change.
The problem is more a psychological one. We just hear about black holes, supernovae, Big Bang, anti-matter, Big Rip etc. all the time because that's simply more interesting. But compared to everything else there is in the universe, those "big" events make up an incredibly small fraction, and the vast majority of things should live a long, happy life of utter boredom and non-change. 
A: The problem is that when you talk about "static" you're implying that there is some universal co-ordinate system to judge these things by. Relativity asserts that no such reference frame exists and therefore the only measures we have for motion etc are dependent on the reference frame that is watching it. Between two comoving objects they will see each other be static, but a third frame moving some other way won't see it that way and the two comoving frames will see the third move.
[by comoving I just mean two objects moving together, not anything GR related]
