I would like to be able to rewrite or reorganize an ELF binary program directly from the executable format (not at compile-time).
I just stumbled on this project ERESI. The project itself looks quite ambitious and supports mainly Intel and Sparc processors with some support for others. There are lots of tools as well that might come in handy. It does have one specific tool that sounds like if fits the bill exactly and quite a few others that are related:
Evarista: A work-in-progress static binary program transformer entirely implemented in the ERESI language.
Patchelf might come in handy for modifying the linker or rpaths specified in an elf:
PatchELF is a small utility to modify the dynamic linker and RPATH of ELF executables
Also there is this presentation about injectso which seems relevate to the topic static and dynamic patching of elf binaries. Admittedly the coverage on static binaries is limited but that is to be expected as it is more complex that just being a library interposer.
If you are looking for libraries specifically then the ERESI project does use alot of libraries so you could probably take Evarista as a guide and write something more in line with your goals with thier libraries.
libelfsh : the binary manipulation library used by ELFsh, Kernsh, E2dbg, and Etrace.
libe2dbg : the embedded debugger library operating within the debuggee program.
libasm : the smart disassembling engine (x86, sparc, mips, arm) that gives both syntactic and semantic attributes to instructions and their operands.
libmjollnir : the control flow analysis and fingerprinting library.
librevm : the Runtime ERESI virtual machine, that contains the central runtime environment implementation of the framework.
libstderesi : the standard ERESI library containing more than 100 built-in analysis commands.
libaspect : the aspect library brings its API to reflect code and data structures in the ERESI language.
libedfmt : the ERESI debug format library which can convert dwarf and stabs debug formats to the ERESI debug format.
libetrace : the ERESI tracer library, on which Etrace is based.
libkernsh : the Kernel shell library is the kernel accessibility library on which Kernsh is based.
libgdbwrap : The GDB serial protocol library, for compatibility between ERESI and GDB/VMware/Bochs/Qemu/OpenOCD.
I think your best bet will be to take a low level ELF library and write a small program to do what you want. I like the ELF Toolchain Project. I've found the tests and documentation that the team puts together to be pretty good. Regardless of what tool you end up using, you definitely want to read A Whirlwind Tutorial on Creating Really Teensy ELF Executables for Linux which discusses how to modify an ELF executable to be as small as possible (your purpose may be different but there are a lot of general lessons to be had).