I learned that for a 4D Minkowski space with a set of basis vectors ${e^\mu}$ the metric tensor is defined as $$g_{\mu\nu}=e_\mu \cdot e_\nu.$$
I would put this a little differently. This reads to me as a definition of one of the components of the metric tensor. You can think of a tensor as the collection of its components (a matrix), and people did used to think about it that way ca. 1940.
But a nicer and more modern way to think about it is that a tensor is a linear function. The metric is a linear function that takes two vectors as inputs and gives a real scalar as an output. It treats its inputs symmetrically, and it has the interpretation of measuring the interval, which can often be interpreted as a squared time or squared distance.
Does this mean that if one choose different sets of basis vectors, the metric tensor for Minkowski space will change?
This would be the 1940 way of describing it. People today would typically say that the metric stays the same, but its components are different when described in the new basis.
What are some examples of the sets of basis vectors that can describe 4D Minkowski space?
For example, you could have one observer's orthonormal t, x, y, z basis, or the t', x', y', z' basis of another observer in a different state of motion. You could have a basis with some null vectors in it. You can have any basis you want, as long as it's linearly independent -- this is the same as for any 4-dimensional vector space.