Sfrgttk

If your tidally-locked planet captured a large moon, sort of like the one we have here on Earth, the tidal forces of the moon could be stronger than the tidal forces from the star. This would result in the planet gradually losing its tidal lock to the star in exchange for a tidal lock with the moon.

No. Not without another body getting involved.

Tidal forces within the planet are constantly pushing it towards the "locked" state, you need a massive input of energy to change that. We're talking really dramatic events.

You might be able to achieve something through a near encounter with a massive body (for example a large rogue planet passing through the system) where there is no collision. However you'd end up with a very elliptical orbit and a second encounter to send it back towards circular would stretch belief rather.

You could achieve the desired effect by having it be a binary planet though. The two planets are locked to each other but each experiences normal day-night sequences. The surfaces facing towards and away from each other could plausibly take on different characteristics.

A planet in our very solar system has actually gone through such a shift! Venus currently has a 243-day long retrograde spin, but likely didn't always. The current theory says it started with the usual fast spin and underwent tidal locking normally. And it would have stopped there, but Venus's thick atmosphere generates thermally driven atmospheric tides which were strong enough to overshoot tidal lock and cause a retrograde spin. Currently its rotation is an equilibrium between the atmospheric tide pushing in retrograde and the sun's tidal dissipation pushing in prograde. See wikipedia's page on retrograde and prograde motion.

Sounds like you aren't particular about keeping the atmosphere... are you cool with a really thick atmosphere? If that's ok, and you don't mind retrograde spin, this one is based on an actual planet. However, I'm not sure how strong that effect would need to be in your scenario.

What if... your tidally locked earth eventually had intelligent life that wrecked their atmosphere...

An extremely powerful nearby pulsar that only hits one edge of the planet.

While this is a rather "out-there" scenario, it's possible for a nearby, very powerful pulsar to repeatedly hit the planet during a small portion of its orbit, but only hit it on one side. This would impart a force to one side of the planet, slowly spinning it up over time the same way you can spin a ball by hitting one side of it.

As a worked example, let's arbitrarily say that the planet takes up a half an arcsecond from the point of view of the pulsar. That's in the same rough angular size as Earth is from Pluto's perspective, so it sounds reasonable. We'll say that the pulsar is as powerful as the Crab Nebula pulsar, so a power of $10^{28} W$ according to this. The pulsar spins, so that half-arcsecond planet is getting hit by one of the two beams a total of $1/296000$ of the time. That translates to getting full power $1/2592000$ of the time, which means that our average power is $10^{28} W / 2592000 = 4*10^{21} W$. If the planet is getting this for, say $1/10000$ of its orbit (I'm just pulling numbers out of my [REDACTED] here, but it sounds reasonable), the average power is $4*10^{17} W$. Now, the rotational energy of the earth is $2.138*10^{29} J$, and our planet is double its mass, so we quadruple the energy (remember, kinetic energy is mass times velocity squared) to come up with a required kinetic energy of $8.56*10^{29} J$. Now, if the pulsar were to transfer energy with perfect efficiency, and we ignore the forces that tidally locked the planet in the first place, this would restart the rotation in $8.56*10^{29} J/4*10^{21} W = 2475 ~days$. We can assume an energy transfer of, let's randomly say 0.00001% because of most of the pulsar beam missing the planet and some of the energy being transferred to heat and translation instead of rotation, that moves the required time up to about 68 million earth years, still within your hundred million year timeframe.

So, in conclusion, my worked example with half the numbers made up and most of the other half being Fermi estimates seems to work. I'm not sure what that level of radio waves will do to a planet, and I doubt it would be pretty or at all nice to any life present, but it seems to work to restart the spin. If anyone has numbers for any of the stuff I completely made up, please comment and I'll change them to actually correct values.

I'd also want the planet's orbit to stay roughly where it is - in the habitable zone.

Does the planet have to start out in the habitable zone? If not, here's a suggestion, in a few stages, involving a gas giant on a very long period, comet-like elliptical orbit:

1. 
   Formation: have the planet initially form on a very close orbit to its star (on the order of several days), where it is tidally locked.


2. 
   Increasing rotation speed: Once the bombardment is done, have the rogue gas giant make a close approach which makes its orbit slightly eccentric, such that the favorable tidal lock is a 3:2 resonance like Mercury, but with a rotation period faster than its current rotation. Give it a few hundred thousand years for the rotation period to stabilize, then have the gas giant swing by again and boost it to a more eccentric orbit where a 5:2 lock is favorable, again with a slightly faster rotation. Repeat until spin is fast enough.


3. 
   Transfer to habitable zone: Close approaches of the gas giant boost its apoapsis past the habitable zone. Allow precession and timing to cause a close approach as it crosses the habitable zone, with your planet moving inward, the gas giant moving outward, and your planet slinging around the sunward side of the gas giant. This is equivalent to a large radial burn and should serve to mostly circularize its orbit in that position.


4. 
   Optional - safety: If the gas giant is on such a long-period orbit, it will go quite far from your sun. A passing star/red dwarf/similarly massive object should be sufficient to divert it from making further passes deep within your solar system and messing up what's been set up.

Referencing this answer.

Based on information in the answer above, liquid planets/moons (like Europa) take much longer to tidal lock. Per the Wikipedia entry for Europa, it may not be fully tidal locked even now. Perhaps a concentration of greenhouse gases caused the frozen surface to melt. Throw in some near misses from other large bodies and you might be able to get the planet spinning again.

I might suggest the introduction of another massive body into the system; rather than an actual impact.

Numerous interstellar planetoids do exist, and every now and then we'll find one or two entering our own solar system. The usual clue that gives them away as extra-stellar is that they have a hyperbolic trajectory, instead of an ellipsoidal one, which can't come about in-system.

If this was a massive enough body, or one that moved slowly enough (though there are restrictions within reasonability there), the perturbation of the gravitational field would cause a tidal effect on the planet, potentially one strong enough to realign its axis of rotation and pull it out of being tidally locked to its host star. Afterward, the planetoid could pass out of the system on its merry way, and the tidal effect would be over.

In most cases, it would take some time to occur; but it would happen as the whole system would be destabilized.

The foreign object could be anything from a particularly large interstellar asteroid to a hypervelocity black hole.

The question doesn't seem to forbid technological methods, so there are a few options there.

The obvious solution would be to put a giant Catherine wheel of angled thrusters around the Equator, and start making the thing rotate. You may want to build a geostationary ring around the planet and link it with the surface with space elevator cables and put thrusters on the circle, in order to avoid blowing the atmosphere away. Keeping the contraption stable and in one piece will require some work, but I assume that's the kind of small engineering problems that won't stop you. You can also replace the atmosphere afterwards (or store it for the duration).

The problem is, you have to overcome the attraction between the tide bulge and the star, so this will require some serious impulse from your planetary thrusters. Which means big, expensive thrusters and the risk of ripping the entire planet apart and turn it into a molten ball of volcanic madness. So the brute force approach is not a good idea.

Instead of trying to make it rotate in one go, you can impart some pendulum movement, pushing in one direction then the other, making it follow the final phase of tidal locking in reverse. At some point, the pendulum movement will be big enough to make a complete revolution, at which point you can simply keep pushing to accelerate to the required rotation speed.

Now, what engines to use? Low-grade mass drivers would make you either dig giant holes in the surface or require lots of mass from elsewhere in the system. You could if you are in a hurry (those are cheap, low Isp/high impulse engines), but that's rather inelegant.

You could use photonic thrusters (aka giant spotlights) if you have good powerplants like matter-energy converters, are in no hurry and there is no-one flying around to be dazzled. More traffic-friendly exotic versions may be possible, for example emitting neutrinos or gravitational waves, in case your neighbours complain about the light show.

There is a middle ground of particle accelerators, requiring much less mass (and being more refined) than the mass drivers, but giving more thrust than pure photonic engines. The simplest version will heat matter into superhot plasma and let it escape by a nozzle at some fraction of c.

Of course, you have a big fusion powerplant already available, so you can take advantage of that. If you are in no hurry, put giant solar sails on your orbital ring and turn it into a (solar) windmill. Feel free to put mirrors all around the star to help concentrate energy on the sails. Or, if you have fancier tastes, put a light Dyson swarm there and have the collectors beam the power with lasers or focused particle accelerators. That may help avoiding cooking the surface with the unfocused mirrors.

Alternatively, if you don't want to build things on the planet itself, put those on local planetoids and move them around. With the right grazing trajectories, you can use gravitational tugging to start making the planet wobble. Once it starts rotating, a low orbit, fast-orbiting moon may help a bit for accelerating it. Be careful to not overdo it, you may cause more volcanisme than desired otherwise.