Let's take a look at the fundamental equation of thermodynamics:
$$
dU = TdS - PdV + \sum_i \mu_i dN_i + \phi dQ + v dp + \dots,
$$
where $U$ is internal energy, $T$ is temperature, $P$ is pressure, $V$ is volume, $\mu_i$ and $N_i$ are the chemical potential and number of molecules of various chemical species, $\phi$ and $Q$ are electric potential and charge, $v$ and $p$ are velocity and momentum, and the dots indicate that there are many other, more exotic pairs of variables that can be added to the end of this equation.
What we're interested in is a change in entropy, so let's rearrange the equation to reflect this:
$$
dS = \frac{1}{T}dU + \frac{P}{T}dV - \sum_i \frac{\mu_i}{T} dN_i - \frac{\phi}{T} dQ - \frac{v}{T} dp - \dots
$$
From this you can see that if you make a small change $dU$ in the energy, while keeping everything else constant, then the entropy will change by $\frac{1}{T}dU$. But also, if you make a small change in the volume while keeping everying else, including the energy, constant, the entropy will change by $\frac{P}{T}dV$. Similarly, you can change the entropy by changing the concentration of any chemical species, or the charge, or the momentum (i.e. by accelerating the system), or by making a change in any other extensive quantity.
The problem is that, in practice, it's not usually very easy to keep the energy constant while changing something else. It's easy enough to keep the temperature constant (you make the change isothermally, i.e. while keeping the system in contact with a heat bath), but that's not the same thing. It's also easy enough (in principle) to keep the entropy constant (you make the change adiabatically and do it very slowly). But generally, in most practical situations, if you try to change one of the other variables you'll also end up changing the energy a bit as well. For example, if you change the volume of a system you do work on it, and that changes the energy. But this is a mere practical issue - it's certainly possible in principle to change the entropy of a system without changing its energy.
Thermodynamics is often thought to be mostly about energy, but when you really get down to it, the role played by energy is no different from that played by any other conserved quantity. Out of all the extensive quantities, the only really special one is the entropy, since it isn't conserved. So for me, the above rearranged version of the fundamental equation is more fundamental than the "fundamental" one.
Another, somewhat unrelated point is that entropy only increases over time on average. For very small systems there are fluctuations, which mean that the entropy can temporarily decrease all by itself. It turns out that you can't use this phenomenon to do work, so the result that you can't build a perpetual motion machine isn't affected by this. To get a feel for fluctuations, consider Boltzmann's result that
$$
S = k \log W,
$$
where $k$ is Boltzmann's constant and $W$ is the number of possible microscopic states the system might be in, given the values for its volume, energy, chemical concentrations, etc. Einstein pointed out that you can invert this to $W = e^{S/k}$ and said (roughly) that the probability of a system fluctuating from a state with $W=W_1$ to $W=W_2$ should be
$$
\frac{W_2}{W_1} = e^{\frac{S_2-S_1}{k}}.
$$
If you plug some numbers into this you'll see that for systems of a macroscopic size will fluctuate by only tiny, unobservable amounts, whereas systems on the scale of molecules fluctuate quite a bit. If the system is isolated then these fluctuations will not change the amount of energy in the system, even though they sometimes temporarily reduce the entropy.
So there are two ways the entropy of a system can decrease without a change in energy: because of a change in another extensive quantity that happens to keep the energy constant; or, if it's a small isolated system, because of a thermal fluctuation.