A fun, but possibly mad and doomed to failure approach would be to mount a distance sensor on a servo and have the robot scan for some notable feature in the environment, either something closer or further than the general environment which could be used as a marker, then have the robot rotate until the marker is detected Y degrees away from its original point.
An even more fun extension of this would be to try a few different senses, so if the robot cannot find a suitable physical object to act as a marker, fall back on light or darkness as a marker.
Lots of limitations - it depends on the marker not moving during the rotation, but is a pretty good approximation of how nature does things.
Above all this is a fun and challenging approach - encoders just aren't that interesting.
Just a suggestion