I've been thinking about how 'const' (C++ style) seems like a good idea but can cause pain in practice. It leads to duplicate definitions of methods (termed a "shadow world" by Anders Hejlsberg). It is really is hard to enforce statically.
See here for some great summaries.
Personally, I think the "bit" idea might work. That is, pointers are usually aligned to 4-byte boundaries. That gives two bits to play with. One of those bits might serve well for indicating constness in a dynamic fashion.
Two different pointers to the same object. One carries const. The other doesn't. Enforcement happens at runtime. Sounds maybe doable.
I'd need to think more about the container issue, though. First thought is that any const pointer is just deeply const.