How does an isolated body in deep space 'know' it's rotating? We can imagine an object floating in the known universe, maximally distant from any other large mass. Maybe it has been there since coalescing after the big bang.
What physical phenomena tell it whether it is rotating relative to the rest of the universe and therefore experiencing a centrifugal (?) force.
Is it the combined gravity of all other matter? Is it 'spooky action at a distance'?  Is it because it is rotating relative to 'empty space'?
 A: In General Relativity, there is no background to spacetime and so there is no absolute reference frame. However, in Special Relativity (SR) there IS a background from which accelerations are absolute. So, Special Relativity is precisely the arena you describe - a space void of matter so that we ignore gravity. There's a nice discussion here. 

What physical phenomena tell it whether it is rotating relative to the rest of the universe 

An observer at rest at the center of the object would not feel any acceleration, but an observer at the edge of the object will feel an acceleration, which they would interpret as a gravitational effect and which is indistinguishable from an inertial force. BUT, this is the essence of Einstein's General Theory of Relativity (GR), where gravity is an inertial effect. 

Is it the combined gravity of all other matter?

Not quite. As Ben pointed out, Minkowski spacetime (with the flat Minkowski metric) is a solution of the Einstein equations of GR, and this is one way of saying that GR is not a fully Machian theory of gravity. What this ultimately means is that local physics of GR is not fully determined by the inertia of the rest of the universe.
So what's going on here? Brans-Dicke theory extends GR and is conceivably more Machian than classical GR since Newton's gravitational constant, $G$, varies over spacetime according to a scalar field $\phi$ which acts as a background. Here, an object rotating in vacuum would be able to "know" it is rotating because if an observer at the COM of the object tracks a point of itself during the rotation away from the COM, then the COM observer would measure different values of $G$ at different positions in the rotation meaning that there was motion, and the observer could deduce that the change in $G$ is due to rotational motion as opposed to linear motion. So what does this mean? Essentially, you've asked a really good question that our best theories of gravity disagree about, since GR fails at relativizing rotational motion (due to the Minkowski asymptotic limit), and Brans-Dicke gravity does provide a background field by which to relativistically detect rotational motion (the scalar field $\phi$).
A: This is a longstanding problem in physics and has not been wholly solved to anyone's satisfaction. It's not just rotational motion, any motion is subject to this concern. Very basically, what is "motion" for a singular object in its own universe?
Mach was one of the first to really explore this issue. He spoke of masses in deep space and wondered if they would have momentum. He concluded they had to, and then went looking for potential solutions to the obvious problem of the lack of any sort of universal ruler.
He concluded that the mass distribution of the universe as a whole (which at that time was the Milky Way remember) forms a sort of momentum background against which all objects, local or no, actually measure against. So even in the case when you're studying the collision of objects on a billiard table, the momentum you measure isn't relative to the table, it's "really" relative to this universal frame, but in the end the table is to so you can reduce it that way.
A more direct solution to the problem was offered by Brans-Dicke theory. This is a theory that is very similar to General Relativity in that it ascribes many things, notably gravity, to the geometry of spacetime. However, it also adds a second linear field that is sort of "baked into" the universe when it is created. This field creates a background reference frame for momentum.
So if BD theory is correct, yes, a universe with a single object in it will definitely feel angular momentum.
Unfortunately, as far as we can tell, BD is wrong. There is no direct evidence of this, but it falls to Occam's Razor. The issue is that BD has a coupling constant (alpha IIRC) that defines how strongly this other field couples to the spacetime - its basically similar to G in normal GR. As it falls to zero, the theory becomes GR in the same sort of way that Newtonian gravity is the weak-field limit of GR.
You can measure alpha indirectly, and to date every new measurement forces it ever closer to zero. So GR wins.
A: It very much depends on the size of the body, it's shape, mass and its distribution, rotation speed, atmosfere and its movements, etc. 


*

*Centrifugal force - is good for relatively small objects which rotate quickly. In an optimal situation, it would create a net force directed outside of the center of the body - in such case the situation is quite clear. However if gravity is stronger than the centrifugal force, you would have to compare the two forces to discover possible anomalies - but then you would need to precisely know the mass distribution to make the calculations properly. Also, the method would not work for large, slowly rotating bodies. After all, do you feel centrifugal force on Earth? It's possible to be measured as on the equator it's 0.3% of the Earth's acceleration, which for 100kg body makes a difference of 0.3 kg between the pole and the equator. So you it's possible to be measured, but you must exclude a number of other factors. 

*A variant of the above: if the body is covered with a liquid, you may try to measure the shape of the surface. And, of course, consider mass distribution inside: a slightly flattened solid globe covered by an ocean could create a gravity anomaly which could be taken for a rotation.

*Pendulum - which could be used to measure acceleration in various parts of the body or to discover the Foulcault effect. But it requires significant gravity mass to work properly - so it's better for large bodies with significant mass, such as of large moons' or planets' sizes. I do not expect it to work properly on a small body, such as an asteroid or ISS. 
In my opinion, these methods seem to be the most universal:


*

*a giroscope - it preserves the constant axis direction in 3d, so by distributing several of them in various parts of the body and pointing in various directions, you should be able to discover the rotation. Please note though that you may have to consider precession in a gravity field.

*Coriolis force - by throwing objects in various directions and at various speeds, and comparing it with straight reference lines you should be able to discover and even measure the rotation. Please note though that the distance should be large enough. On Earth at distances of few kilometres the effect is barely measurable. The method is prone to errors caused by atmosferic movements (winds), I also doubt if you could discover it if the solid surface is covered with a liquid. In such situations you can observe large scale tendencies in atmosferic movements (cyclones, anticyclones, currents in liquid, etc). 

*A variant of the above: you can shoot an object straight up, exactly opposite to the direction of the local gravity force. If it does not fall down at your shotgun, it may mean that the barrel is skewed, or the body is rotating (and you're not on the pole). 

*You may also send a few satelites at various hights and measure direction and strength of thrust you need to apply to keep them exactly over a selected point on the surface.
So although all methods are prone to errors and may require solving practical problems, especially with precise measurement, there are quite a few methods, and none of them depends on external frame of reference.
A: Scientifically, there's no reason to expect rotational velocity to be relative. To see why, think about linear velocity first.
Historically, we start with Aristotelian physics, which states that linear velocity is not relative; objects have a preferred rest frame. Then we get Galilean physics, where linear velocity is relative. 
Why do these theories say different things? If you work within the theory, Aristotle will tell you that objects wish to go to their "natural state of rest", while in the Galilean framework one might say speak of "Galilean symmetry", or 
 inertial frames and Newton's first law. There's a lot of high-minded theory and big words on both sides, but what it really all comes from is experimental data. Aristotle observed that a flying arrow will always come to rest. Galileo argued that one could not detect velocity inside a moving ship. Their theories differ because they started from different observations about the world.
Of course today Galilean physics is known to be right, but it's important to remember the order of logic here. We did not conclude velocity is relative because the world has Galilean symmetry. We observed that velocity is relative, then described that observation using Galilean symmetry. It is by no means the only option; the world could have turned out another way. 
So if you try to extend the pure, theoretical arguments of Galilean symmetry to claim that linear acceleration is obviously relative too, you're getting it completely backwards. Linear acceleration is simply different from linear velocity. You don't know anything about it a priori, you have to go outside and see. There you notice that you can tell when a train is accelerating even with your eyes closed, so linear acceleration is not relative.
Now consider rotational velocity. One might naively say rotational velocity is just the same thing as linear velocity, because they're both called velocities. But from the standpoint of each particle in a rotating body, rotation is merely a particular, periodic pattern of linear acceleration. So since rotational velocity has similarities to both linear velocity and linear acceleration, which theoretical arguments should we apply to it? Answer: neither. Once again, we have to go out and check, and once we do, we find rotational velocity is not relative. 
That's the end of the story. You might think, as Mach did, that the universe would have been more symmetric, more logical, if rotational velocity had been relative. But it just isn't that way, and you don't get to impose a symmetry on Nature it doesn't have by force. That's not how science works.
A: If you are talking about the rotation of the body around its Centre Of Mass, it could be detected, because different parts of the body will have different acceleration and, therefore, there will be internal forces, which could be measured, at least, theoretically.
If you are talking about the rotation of the body relative to some remote mass due to its gravitational pull, it would be a free fall and it would not be detectable, because all parts of the body will experience the same acceleration and would have no internal forces between them to be measured. 
A: One thing you could do it set up a Foucault's pendulum. Another is look at a gyroscope in free fall near to you as you sit on the object. Another is put little dust particles near to the object, with no force on them as far as you can tell, and let them go, and see how they move relative to the object.
Your question touches on some quite deep aspects of physics, which go by the name 'Mach's Principle'. This is not a precise law of nature, but rather some notion that the local definition of what is inertial motion and what is not is connected to the large-scale distribution of the distant matter (galaxies etc). General Relativity certainly includes the idea that what motion is inertial is connected to how matter is laid out, including at the largest scale, but it is a matter for continuing debate whether or not this fully captures Mach's Principle.
In the case of a body that we say is rotating, we could, if we wanted, say that it is not rotating but is subject to an unusual sort of gravitational field which causes the results of all the experiments with Foucault's pendulum and gyroscopes and so on. However, this would be an odd point of view to take.
A: The effect of centrifugal force is fictitious (it doesn't exist.) What you feel when being rotated around a point and you are holding onto a string is a centripetal force. When you have circular motion, your direction of movement at a given time is tangent to the circle. So, if you let go of the string, you would keep moving in a direction that was tangent to the point of the circle you let go at. The "centrifugal force" you feel is just the force of the string preventing you from continuing straight. So, the reason you feel a centrifugal force is because Newton's first law states that "an object in motion will stay in motion", so the object going around in a circle wants to go straight but is stopped by the string, which causes it to move around the circle.
Now, back to the original question. Newton's laws of motion, in this case, the first law, can only work from a reference frame that is not accelerating. For example, if I hop into a car and start accelerating, then relative to the earth I am accelerating, and would thus feel a force, but relative to me the earth seems like it is accelerating, but not everyone on earth feels a force in my direction, so therefore the laws can only work in a reference frame that is not accelerating. Since we cannot 100% guarantee whether or not the universe is accelerating, then we cannot say that the object would experience a centrifugal force relative to the universe and that the universe would feel this centrifugal force, but we can for sure say that the object feels a centrifugal force.
A: Simply put, even the empty spacetime has a metric structure which lets the object know if it is in an inertial frame or not, and consequently, if it is rotating or not.  
The idea that you need a visible object and only then you can tell (via comparison to it) whether you are in motion or not is really misleading. Such an idea can only work to tell you whether you are in a relative motion w.r.t. the object you are comparing yourself to. But, as General Relativity has made clear, there is an absolute meaning to certain aspects of motion. In particular, talking about acceleration or a lack of it makes sense even when no frame is specified--because it is apriori clear which frame to measure it with respect to, namely, the locally freely falling frames. The existence of such frames is geometrically described by in terms of the metric structure of the spacetime which is such that you can always construct a local reference frame which makes the affine connections vanish and the metric Minkowskian.
Notice, in contrast, the fact that you can never provide such a canonical description of "How to go to a local frame which is at rest?" because there are no special rest frames. All the Minkowskian frames are completely equivalent. This amounts to saying that talking about velocity or a lack of it makes sense only when a specific reference frame has been specified.   
A: I think that, just like all motion, rotation is relative, but I may be wrong. 
Every point on a rotating body thinks the body is rotating around IT, but it's only the point at the center of mass (or the pivot) which feels like its stationary relative to the universe. Let me give an example: 
Imagine this circle is the entire universe. There's nothing more than this circle:

Okay, now there's something more than the circle. The god of physics stack exchange said let there be a rod, and now you also see a single black horizontal rod. 

Each of the colored blobs on the rod is a different point which the rod could rotate around. This view is from the point of view of a hyperdimensional being, watching from the outside of the universe (outside the universe because they're staring down at the paper).

The rod could rotate around the red point....

Around the pink point...

or around the blue point...

Now, let's consider ourselves as being really small. Extremely small. We shrink smaller and smaller, and all of a sudden are teleported to the pink point. 
Recall that the circle represents the entire universe the rod exists in; there is nothing more but the rod and the circle (ring, universe, whatever). Period.  
Oh, and there's also no gravity. And no oxygen. We don't need to breathe. 

Now, the rod rotates “around” the blue point. From the point of view of an otherworldly outsider that exists outside the universe, that's exactly what it does. It rotates around the blue point.

But what about us, standing on the pink point? If the rod rotates fairly quickly, we'll feel an increase in the normal force from the rod. And thus we'll be able to tell its the rod that's moving and not the world around us. (Ignore the picture in bottom right, that was a mess-up)

BUT, IF the rod rotates really slowly... then what we might really think is that the rod rotated around us (around the pink point) counter-clockwise, but simply also pulled the ring (universe) along with it! There really is no difference! 
We would actually think the rod rotated around us, but it was simply attached to the circle at the blue point, attached to the universe at the blue point, and looks like this:

We can do this for the other scenarios as well. In fact, for every rotation, we can pick any arbitrary point on the rod and say that the rod rotated arount it, its just only ONE of those points will think the universe was still as well. All the others will simply think the universe was attached to the rod at some other point, and rotated with it.
Let's look at a rotation where we agree with the hyperdimensional viewer staring down at the paper (if the circle is the entire universe...what's the paper?!). 
In the rotation where (to the viewer looking at the paper) the rod rotates “around” the pink point, to us (“standing at the pink point”) the rod rotated around the pink point as well!

In this rotation, the universe was still relative to us (to the pink point). And we thought the rod rotated around us.
But these are two separate statements. We could've thought the rod rotated around us in any scenario, simply only in one will the universe be still relative to us as well.
This was the difference between this and the last rotation: that in this rotation, the universe was still relative to us, while in the last one, we saw it move with the rod. But we think that the rod rotated around us regardless of the situation, simply that in the first scenario the rod was for some reason attached to the circle (universe) at the blue point and thus it rotated around us as well. 
But what if there was no universe? What if there was no circle?
If there was no universe for the rod to rotate in, from the point of view of the person looking down we would be the only point of reference, they may very well agree that the rod rotated around us (pink point) in the first scenario as well! Then if we add the ring, they may agree that the ring was connected to the blue point, and got pulled along with it! 
Rotation is relative
Finally, when the rod rotates “around” the red point from the point of view of the hyperdimensional viewer, to us (“standing at the pink point”) everything rotated around us again, we were the center of rotation, and it's just the red point pulled the universe with it upwards and to the left!


Either way, in all three scenarios, we can say the rod spun around an arbitrary point on the rod. That is, it spun around us. It's just in some scenarios, the universe followed along.
We are the center of everything, and the universe spins around us.
But if the universe wasn't there to begin with, then yes, there would be no circle to rotate relative to, and there would indeed be no way to tell which point the rod was rotating about.   
Happy thoughts! The universe rotates around you! 

Hope that helped.
