One thing to keep in mind is that objects that are bound gravitationally actually revolve around each other around a point called a barycenter. The fact that the earth looks like its revolving around the sun is because the sun is much more massive and its radius is large enough that it encompasses the barycenter. This is a similar situation with the Earth and Moon. If there were three bodies, where two bodies were of similar size (like a binary star system plus a massive planet) then an analysis of three body systems shows that there are stable configurations where the objects will be in very complicated orbits where it would be difficult to say one orbits the other.
Update: The short answer is yes, it is possible when you look at the complete dynamical system, for the reasons stated above. More evidence of this can be found in the study of regular star orbits where very complicated orbits are possible and can be stable. Currently the cut off for classification of a planet and a brown dwarf is 13 Jupiter masses, which is arbitrary to some degree. The lightest main sequence stars have a mass of 75 Jupiters. This will put the barycenter well outside the radius of either body for binary systems.
A quick check of the two body system using the equation:
$$R = \dfrac{1}{m_1 + m_2}(m_1r_1 + m_2r_2)$$
Setting $m_1 = 75$, $r_1 = 1$, $m_2 = 13$, $r_2 = 2$ gives:
$$\dfrac{75 + 26}{75+13} = 1.147$$
Indicating a barycenter at roughly $\dfrac{1}{7}$ the distance between the objects. More bodies will cause more complicated orbits, where again, it would be difficult to say which object orbits which. It should be noted that if the system was composed of 3 objects, 2 of which had similar mass, it would be possible to develop a system that appears to have two larger objects orbiting a third smaller object. A quick check reveals:
$$R = \dfrac{1}{m_1 + m_2 + m_3}(m_1r_1 + m_2r_2+ m_3r_3)$$
Setting $m_1 = 75$, $r_1 = 1$, $m_2 = 13$, $r_2 = 2$ $m_3 = 75$, $r_3 = 3$ gives:
$$\dfrac{75 + 26 + 225}{75+13+75} = 2$$
Whether such an orbit system is realizable when you consider the full dynamics of a natural system is debatable, but I am not aware of a specific proof that would rule it out.
UPDATE
It should be noted that there are new periodic solutions to 3-body problems when the objects have the same mass.
You mean like Arthur C. Clarke's 2010 when Jupiter turns into a star? We often turn to Jupiter's mass ($M_j$) when thinking about this problem.
It turns out there's a whole class of stars that fuse so faintly that we can only see them well in infrared. Brown dwarfs (which are still called "stars") turned out to be so cool that only new infrared technologies could find them. We now know they are very common, so common that new classes, L and T (cooler than M) had to be made for them. Surprisingly they turn out to be about the same diameter as Jupiter. Between 0.073 solar masses (78 Jupiter-masses) and 13 Jupiter-masses, brown dwarfs do fuse their natural deuterium (heavy hydrogen, with an extra neutron) to helium. Below 13 Jupiters (0.0124 solar masses), fusion stops altogether.
The brighter stars like our sun begin above 0.073 solar masses where they are hotter and emit more visible radiation.
So you need at least 13 Jupiters to get it going and the theoretical limits are still being refined by observations of Brown Dwarfs. There is a fussy line between planets and brown dwarfs. Small brown dwarfs can still be considered stars and not planets even if they are not fusing because they probably burned off all their deuterium (form of hydrogen).
From Wikipedia:
Currently, the International Astronomical Union considers an object
with a mass above the limiting mass for thermonuclear fusion of
deuterium (currently calculated to be 13 Jupiter masses for objects of
solar metallicity) to be a brown dwarf, whereas an object under that
mass (and orbiting a star or stellar remnant) is considered a
planet.
The 13 Jupiter-mass cutoff is a rule of thumb rather than something of
precise physical significance. Larger objects will burn most of their
deuterium and smaller ones will burn only a little, and the 13 Jupiter
mass value is somewhere in between. The amount of deuterium burnt also
depends to some extent on the composition of the object, specifically
on the amount of helium and deuterium present and on the fraction of
heavier elements, which determines the atmospheric opacity and thus
the radiative cooling rate.
Best Answer
This should be physically possible, it even might happen in the universe right now.
The creation of a stellar system starts with a cloud of matter. This cloud will collapse and form some kind of thing we later might call a star. You might also call this a planet - if the mass is not enough to create a pressure which is high enough to make an initial fusion, you will have a brown dwarf. Also Jupiter is a planet which is a "too light" star.
In my opinion, nothing speaks against the possibility, that maybe two "clusters" forming at the same time. Or a smaller cluster forms first and a bigger - which becomes the star later - forms second.
The point here is more, what you call a planet? Is the sun a planet? Would be Jupiter a planet, if it shines like a star? Maybe you can call the sun a planet, if it rotates around some bigger mass? There might be some sort of definition to be done for this, I think.