You need "side effects" to include memory allocation, seg faults, and "significant" amount of computation time (including never terminating). Worse, you need these properties when the program is known to be in an error state.
For a general purpose programming language this means that your toString cannot be a normal function.
Also good points, I suppose the printing mechanism couldn't use the type's implementation of toString() and would instead have to use an implementation built into the runtime. Still, even being able to see just the raw bytes would be better than nothing in a lot of cases.
Of course, this is probably only remotely feasible in languages that can guarantee that toString() won't have any side effects.