Try running the .run with --keep, then cancelling the update after the
README is listed. This will leave you with a directory with the whole
patch thing.
Then, download the loki_patch at
http://www.icculus.org/~msphil/loki/x86/
and overwrite the one buried in the patch directory's hierarchy with this
binary.
Once that's done, run the (probably) update.sh immediately inside the
patch directory, and see if that works.
This worked for me.
Or create this script.
#!/bin/bash
INSTALLDIR=/usr/local/games/<your game>
TMPD=t2tmp
mkdir $TMPD
tail +179 <your game>-cdrom-x86.run | tar -C $TMPD -xvzf -
cd $TMPD
bin/Linux/x86/loki_patch patch.dat $INSTALLDIR