I finally managed to compile kpdfview that would work on kindle using CS/MG 2012.03-57 toolchain. I was going to write a lengthy post listing all the things that I tried (and failed), but in the end I decided not to waste everyone's time. Instead, I'll just give final working solution.
1. copy stdio.h from 2007q3 over 2012.03's stdio.h in /opt/arm-2012.03/arm-none-linux-gnueabi/libc/usr/include. (You can probably use stdio.h from kindle source, but I didn't try this. If you use header from kindle source, it might need to be adapted https://github.com/hwhw/kindlepdfviewer/issues/103
2. copy /usr/lib/libstdc++.so.6.0.8 from your kindle to your pc. Rename it to libstdc++.so.6.0.16 and copy it over existing file in /opt/arm-2012.03/arm-none-linux-gnueabi/libc/usr/lib/. (You can probably copy it without renaming, but then you'd have to delete libstdc++.so.6 and libstdc++.so and remake them to link to libstdc++.so.6.0.8. I find renaming easier).
And that's it. KindlePDFViewer will now compile with 2012.03-57, and this time, it WILL work on Kindle. I suppose this will work on other versions too (from 2008q3-41 to 2011.09-70) but I didn't try it.
Oh, I forgot to mention: you don't need to use STATICLIBSTDCPP when compiling. It will link dynamically.
Update: As NiLuJe pointed out bellow, this is an ugly hack. Do not use it. Use this instead.