cren - if your aim is to make it near-invisible, you might experiment with dynamicaly linked libraries (DLL's).
If every independent piece of code (all the way down to a function) is in a seperate library, then calls from one function to another go indirectly, via a 'jump table'.
Now, for every function which is not in memory, you can have the entry in every corresponding 'slot' in the jump table point at your code. Your special jump-table function will get called when a function calls another, but the target function isn't loaded. Your code loads the missing function, and fixes the jump-table accordingly. If your code has to evict a function, it wires itself into the call slot for the evicted function. A trick here is to know that a function is not in the middle of a call, and going to be called when the stack unwinds.
The basic mechanism exists in the compiler, linker and dynamic loaders, so you'd have a pretty slick, near invisible technique to handle program code loading.
But be aware stack unwind isn't an issue for the existing tools and technology, so you'd need to come up with an approach. You could just search down the stack for a number which looks like the start address of the function you've chosen to evict, and if it isn't there, go ahead, and throw it away. The stack is word aligned (or 8-byte aligned) so looking isn't too arduous. There is a small chance that you keep a function unnecessarily because there is a number on the stack which corresponds to the functions address (4,294,967,296 to one?-) but that is safe.
This won't be as easy as I might have made it sound, but it could be interesting.
EDIT: I made a significant mistake.
The return address on the stack points to various points within the function (which is a candidate for eviction), not just at its start. So a search for a return address on the stack would look for a range of values, and not a single value. This makes the odds of a mistake higher, and is a slower search.