If you disable gdm, you can do this using startx and VT switching. You may have to specify a different display, eg,
startx -- :1 but it all refers to the same physical device if you only have one set up.
For example: User A logs in on VT 1, begins an X session with
startx. Now switch to VT 2 via Ctrl-Alt-F2, and log in as user B, then
startx. If you get a message, "X server already running on display 0:0" use
startx -- :1.
You can now switch back and forth between the two X sessions, owned by two different users with completely different DEs, etc, by just switching VT's. Painless and instantaneous. You don't have to log out of either of them, although if security is a concern and these are two different people you will want to lock your screen; the VT switching should still be okay (I generally don't do the screen locking since I use this by myself, so YMMV).
I also don't use gnome, so I can't say for this will work with all DEs. It definitely will not with any kind of GUI login (GDM, XDM, etc.) system active, you have to boot to console, login, startx.
On some systems this works out in a very straight-forward way: you log in on VT 1, your X session is also on VT 1, and same for VT 2. On others (or I've noticed, occasionally on the same...) the X session ends up on a separate VT, meaning you have to sort that out each time and you will end up using two VTs per user.