How to force a window into fullscreen mode via xrandr and override_redirect was explained somewhat in the last blog past. That method however has limitations, it expects the window to be of the right size and aspect ratio and that you actually can switch to a fitting resolution with xrandr. Not to big a problem with your average 800x600, but some uneven resolutions such as 960x600 (320x200 with a 3x scaler) can often give trouble, either not being supported at all or displayed incorrectly on a LCD.
How to fix the situation in theory is easy, you pick the closed resolution to the target, move the window into the center of the screen, instead of the the top left and just display a black border around the window to get a letter boxed view. Implementing that in practice is a little more complicated, as getting two windows above the panel and into the right order is a little ugly.
There is however a nice way to handle the situation, you can have one XWindow essentially swallow another XWindow. This works via XReparentWindow() or in PyGtk terms with gtk.gdk.window_foreign_new(), to get a GdkWindow from a WindowId, and then with a gdk.Window.reparent() call. That way one ends up with a window containing the other application and that window can be resized or fullscreen like a regular window, so it is very simple to get it where one wants it to have.
There are still some unsolved bits left: I haven't yet managed to give the swallowed window keyboard focus, in only receives mouse events. Not sure if that is something that can be fixed via PyGtk or if I have to switch to more low level Xlib coding.
Another more simple alternative solution that I haven't played with: One can launch a child Xwindow server, such as Xephyr, set a X11 background color, start the application in that. All that without a window manager, so one would just need to position the window properly in the server. That would however not be as flexible and Xephyr can't do window resize right now.
GtkPlug and GtkSocket are another alternative, they are, in theory, build to handle this window swallowing in a nice wrappered up GtkWidget form, but so far I didn't had much success in actually using them, as they fail for exactly the same reason as gdk_window_foreign_new() is causing trouble.