Using gotos, it would look something like this:

    state1:
      /* do some stuff */
      if (/* something or other */)
        goto state2;
      else
        goto state3;
    state2:
      /* do some stuff */
      goto state1;
    state3:
       ...

The labels represent states, and the gotos represent transitions.

You're right that this isn't particularly good for implementing virtual machines, but for more "fixed" types of state machines this can be a pretty clear way of representing them in code. Mike Pall wrote a good overview of various virtual machine techniques here: http://lua-users.org/lists/lua-l/2011-02/msg00742.html (while he knocks the performance of the switch-based approach, I'd like to note that it's the most portable).

> When you remove something essential from a programming language, you are forced to reinvent it; actually, more complex version(s) of it.

That's a good way of phrasing it. It almost sounds like a lemma to Greenspun's Tenth Rule :)