Quick review (in anticipation of more code).

The main issue I have with the code is that is not encapsulate in a class.

std::vector<Element> data;       // usual continious vector, no magic here
std::vector<int> key_indices;    // point to data[]. these values changes when erase/insert to data
std::vector<int> free_indices;

These are basically global variables and anybody can access an mutate them (not just maliciously but accidently). C++ has the ability to encapsulate all the parts of a class and protect it from accidental misuse by only allowing certain functions (methods) to access the raw underlying data.

class MultiIndexToElement
{
    private:
        std::vector<Element> data;         // usual continious vector, no magic here
        std::vector<int>     key_indices;  // point to data[]. these values changes when erase/insert to data
        std::vector<int>     free_indices;
    public:
        void emplace_back();
        Key get_key(std::vector<Element>::iterator iter);

        Value& operator[](Key key);            
        Value& operator[](int index);
        
        void erase(std::vector<Element>::iterator iter);

     private:
        template<class iter>
        void update_indices(iter from, iter to, int shift);
};

Now that we can see the interface clearly there are a couple of things you should watch for.

###Const correctness.

A method that does not change the state of the object should be marked const. This tells the compiler that calling this method does not change the object.

      Key get_key(std::vector<Element>::iterator iter) const;
                                                  //   ^^^^^

This is important because objects get passed to functions by const reference a lot in C++ to avoid the cost of copying the object.

###Element Access

Usually containers allow tow forms of element accesses. Mutating access and const accesses.

        Value&       operator[](int index);       // This allows mutating access.
        Value const& operator[](int index) const; // This allows const accesses.

###Emplace Back.

Usually emplace back (a new form of push back). Creates the Element in place using one of Elements constructors. Your version only allows for Element to have zero parameter constructor.

It is usually written like this:

 template<Args... args>
 void emplace_back(Args const& args...) {
     data.emplace_back(args...);     // pass arguments to constructor
     .... /* Other stuff you need */
 }

The Args... part is a new part of C++14 so you will need to tell your compiler to use the newer version of the standard (that's not a default yet). But usually this means adding -std=c++14 to the command line.

###Templatization

Your code does not allow for easy templatization. In fact you don't define Value in the code sample above. This is more easily solved using templates around a class.

template<typename Value>
class MultiIndexToElement
{
     /* STUFF */
};