It depends. It's all a matter of what changes and what doesn't, as much as a certain symmetry in how these things (space and time coordinates) change.
You can arrange to have space-time transformations that do not make the speed of light an invariant, but do not give absolute simultaneity of events.
In standard special relativity, all the kinematical (having to do with motion) results are contained in the Lorentz transformations: $$ t'=\frac{t-vx/c^{2}}{\sqrt{1-v^{2}/c^{2}}} $$ $$ x'=\frac{x-vt}{\sqrt{1-v^{2}/c^{2}}} $$ where $\left(t,x\right)$ and $\left(t',x'\right)$ are the time and space coordinates corresponding to inertial frames moving with relative speed $v$, and I'm assuming, for simplicity, that everything takes place in one spatial direction, $x$. It's not difficult to deduce from here that if an object moves with speed $v_x$ in the unprimed reference frame (S), it will be seen as moving at speed, $$ v_{x}'=\frac{v_{x}-v}{1-vv_{x}/c^{2}} $$ in the primed reference frame (S').
Suppose an observer at S sees an object moving at speed $c$: $$ v_{x}=c $$ Then, an observer at S' will see it moving at speed: $$ v'_x=\frac{c-v}{1-vc/c^{2}}=c\frac{c-v}{c-v}=c $$ This is the famous invariance of the speed of light.
Now you can try to generalise this. Suppose Lorentz's transformations displayed above were not exactly correct. Let us assume instead, $$ t'=f\left(v\right)\left(t-g\left(v\right)x/c^{2}\right) $$ $$ x'=f\left(v\right)\left(x-cg\left(v\right)t\right) $$ for certain universal functions $f\left(v\right)$ and $g\left(v\right)$ characterising the relative motion between S and S'. Assume also that you have two events separated by time interval $\Delta t$ and space interval $\Delta x$ in frame S. You would have, $$ \triangle t'=f\left(v\right)\left(\triangle t-g\left(v\right)\triangle x/c^{2}\right) $$ $$ \triangle x'=f\left(v\right)\left(\triangle x-cg\left(v\right)\triangle t\right) $$ and, $$ v'_{x}=\frac{\triangle x'}{\triangle t}=\frac{f\left(v\right)\left(\triangle x-cg\left(v\right)\triangle t\right)}{f\left(v\right)\left(\triangle t-g\left(v\right)\triangle x/c^{2}\right)}=\frac{\frac{\triangle x}{\triangle t}-cg\left(v\right)\frac{\triangle t}{\triangle t}}{\frac{\triangle t}{\triangle t}-g\left(v\right)\frac{\triangle x}{\triangle t}/c^{2}}=\frac{v_{x}-cg\left(v\right)}{1-g\left(v\right)v_{x}/c^{2}} $$ This transformation law for velocities still gives you an invariant speed of light:
$$
v'_{x}=\frac{\triangle x'}{\triangle t}=c\frac{c-cg\left(v\right)}{c-cg\left(v\right)}=c
$$
So the idea is that you would have to play with these $f$ and $g$ $v$-dependent factors to make them non-symmetrical between space and time, and you would arrive to a freakish space-time in which simultaneity of events would not hold, and yet the speed of light would not be an invariant. So yes, it is a logical possibility. It would meet all kinds of problems with homogeneity and isotropy, but that's another story.