Structures of function pointers and, what, string method names? My C++ is rusty, but that's all I can think of. I guess there's a lot of variations on structures of pointers...
Templates and compile-time polymorphism. This is what the STL is based upon. A forward iterator is any type for which the * and ++ operators are defined; you can use it in any template that makes use of just those syntactic forms, but will get a compiler error if you try to instantiate a template with a type that does not support those operators.
Punning on memory layouts, a la PyObject_HEAD or some of the objects in V8. With this approach, you make sure that all related types have the same memory layout for a subset of fields at the beginning of the struct. Then, a reinterpret_cast on a pointer to one member of the type will yield the same values as a different member of the type, and so can be used generically by code that depends only upon those members. (You have to be very careful with this approach, because multiple inheritance and vtables will usually break it, but if you absolutely positively must have zero-overhead runtime polymorphism it's occasionally the best option.)
#include and preprocessor magic to redefine symbols based on preprocessor defines. Used to be the old way to swap out different implementations of a cross-platform interface, but seems to have largely fallen out of favor in the last couple decades.
Linker magic to accomplish the same, where the header file defines a common interface but the linker may link with one of several different object files to implement that interface at link time. This one is still fairly commonly used; Google and Facebook both have their own custom STL & libstdc++ implementations, and this is also commonly used to swap out eg. malloc implementations.
dlopen & dlsym to do this at runtime. Header file defines the interface, dlsym gives you back a function pointer or set thereof for a plugin implementation.
In Sean Parent's 'Inheritance is the base class of evil' talk Sean outlines an interesting way to achieve runtime polymorphism without inheriting interfaces in C++.
