Okay, it turns out this actually fixed it, so long as I run it from Steam.
So basically just remove Steam's 32bit libgcc and libstdc++, and the libz and libgcc provided with RunningWithRifles.
Code:
mv ~/.local/share/Steam/ubuntu12_32/steam-runtime/i386/lib/i386-linux-gnu/libgcc_s.so.1{,.disable}
mv ~/.local/share/Steam/ubuntu12_32/steam-runtime/i386/usr/lib/i386-linux-gnu/libstdc++.so.6{,.disable}
mv ~/.steam/steam/SteamApps/common/RunningWithRifles/lib/libgcc_s.so.1{,.disable}
mv ~/.steam/steam/SteamApps/common/RunningWithRifles/lib/libz.so.1{,.disable}
I hope it helps others too, and thanks for making a Linux version!