Increasing the gain of a BJT amplifier without affecting dc bias
Yes, you are right, decreasing \$R_\textrm{E}\$ would increase gain, but this would violate your constraint "without changing DC bias".

In that circuit in-band voltage gain is basically \$A_\text{v}=-g_\text{m}R_\text{C}\$
-it should be RC||RL, but the latter is not given, I assume is open circuit- 

Then \$g_\text{m}=I_\textrm{C}/V_\text{T}\$ and finally \$I_\text{C}\approx I_\text{E}=V_\text{E}/R_\text{E}\$ as long as we do not drive transistor out of active region. 

So putting all toghether $$A_\text{v}\approx - \frac{V_\text{E}}{V_\text{T}}\,\frac{R_\text{C}}{R_\text{E}}=
-\frac{2.13\,\text{V}}{26\,\text{mV}}\times\frac{1\,\text{k}\Omega}{560\,\Omega}\approx -145$$ with your numbers

and indeed lowering \$R_\textrm{E}\$ increases gain BUT you have to consider also that this is surely  going to reduce output dynamics (i.e allowed output voltage swing), everything in life is a tradeoff. 

Also, generally,  take care to verify reduced \$R_\textrm{E}\$ will extra load base bias voltage divider with changes in \$V_\textrm{E}\$ too (your circuit has quite heavy divider though).

Finally, note as we don't need any BJT parameters (e.g. \$\beta\$) to make rather accurate gain calculations, that's a well-engineered circuit!