Formal Definition of Dot Product In most textbooks, dot product between two vectors is defined as:
$$\langle x_1,x_2,x_3\rangle \cdot \langle y_1,y_2,y_3\rangle = x_1 y_1 + x_2 y_2 + x_3 y _3$$
I understand how this definition works most of the time. However, in this definition, there is no reference to coordinate system (i.e. no basis is included for the vector components). So, if I had two vectors in two different coordinate systems:
$$x_1 \vec{e_1} + x_2 \vec{e_2} + x_3 \vec{e_3}$$
$$y_1 \vec{e_1'} + y_2 \vec{e_2'} + y_3 \vec{e_3'}$$
How, would I compute their dot product? In particular, is there a more formal/abstract/generalized definition of the dot product (that would allow me to compute $\vec{e_1} \cdot \vec{e_1'}$ without converting the vectors to the same coordinate system)? Even if I did convert the vectors to the same coordinate system, why do we know that the result will be the same if I multiply the components in the primed system versus in the unprimed system?
 A: The coordinate free definition of a dot product is:
$$ \vec a \cdot \vec b  = \frac 1 4 [(\vec a + \vec b)^2 - (\vec a - \vec b)^2]$$
It's up to you to figure out what the norm is:
$$ ||\vec a|| = \sqrt{(\vec a)^2}$$
Here is a reference for this viewpoint:
http://www.pmaweb.caltech.edu/Courses/ph136/yr2012/1202.1.K.pdf
Section 2.3
A: On computing the following matrix will give you the dot product $$\begin{bmatrix} x_1 & x_2& x_3 \end{bmatrix}.\begin{bmatrix} e_1.e'_1 & e_1.e'_2 & e_1.e'_3 \\ e_2.e'_1 & e_2.e'_2 & e_2.e'_3  \\ e_3.e'_1 & e_3.e'_2 & e_3.e'_3\end{bmatrix}.\begin{bmatrix}y_1\\y_2\\y_3\end{bmatrix}$$ If we transform the cordinate of the a vector, only the components and basis of vector changes. The vector remains unchanged. Thus the dot product remain unchanged even if we compute dot product between primed and unprimed vectors.
A: Your top-line question can be answered at many levels.  Setting aside issues of forms and covariant/contravariant, the answer is:

The dot product is the product of the magnitudes of the two vectors, times the cosine of the angle between them.

No matter what basis you compute that in, you have to get the same answer because it's a physical quantity.
The usual "sum of products of orthonormal components" is then a convenient computational approach, but as you've seen it's not the only way to compute them. 
The dot product's properties includes linear, commutative, distributive, etc.  So when you expand the dot product
$$(a_x \hat{x}+a_y \hat{y} + a_z \hat{z}) \cdot (b_x \hat{X}+b_y \hat{Y} + b_z \hat{Z})$$
you get nine terms like $( a_x b_x \hat{x}\cdot\hat{X}) + (a_x b_y \hat{x}\cdot\hat{Y})+$ etc.  In the usual orthonormal basis, the same-axis $\hat{x}\cdot\hat{X}$ factors just become 1, while the different-axis $\hat{x}\cdot\hat{Y}$ et al factors are zero.  That reduces to the formula you know.
In a non-orthonormal basis, you have to figure out what those basis products are. To do that, you refer back to the definition:  The product of the size of each, times the cosine of the angle between. Once you have all of those, you're again all set to compute. It just looks a bit more complicated...
A: Dot products, or inner products are defined axiomatically, or abstractly. An inner product on a vector space $V$ over $R$ is a pairing $V\times V\to R$, denoted by $ \langle u,v\rangle$, with properties $\langle u,v\rangle=\langle v,u\rangle$, $\langle u+cw,v\rangle= \langle u,v\rangle+c\langle w,v\rangle$, and $ \langle u,u\rangle\gt0$ if $u\ne0$. In general, a vector space can be endowed with an inner product in many ways. Notice here there is no reference to a basis/coordinate system. 
Using what is called the Gram-Schmidt process, one can then construct a basis $\{e_1,\cdots e_n\}$ for $V$ in which the inner product takes the computational form which you stated in your question. 
In your question, you are actually starting with what is called an orthonormal basis for an inner product. The coordinate-free approach is to state the postulates that an inner product should obey, then after being given an explicit inner product, construct an orthonormal basis in which to do computations. 
In general, an orthonormal basis $\{e_1,e_2,e_3\}$ for one inner product on $V$ will not be an orthonormal basis for another inner product on $V$.
A: The dot product can be defined in a coordinate-independent way as
$$\vec{a}\cdot\vec{b}=|\vec{a}||\vec{b}|\cos\theta$$
where $\theta$ is the angle between the two vectors. This involves only lengths and angles, not coordinates.
To use your first formula, the coordinates must be in the same basis.
You can convert between bases using a rotation matrix, and the fact that a rotation matrix preserves vector lengths is sufficient to show that it preserves the dot product. This is because
$$\vec{a}\cdot\vec{b}=\frac{1}{2}\left(|\vec{a}+\vec{b}|^2-|\vec{a}|^2-|\vec{b}|^2\right).$$
This formula is another purely-geometric, coordinate-free definition of the dot product.
A: A vector space (or linear space) is a set and two operations, which are vector addition and scalar multiplication, and some rules (spelled out in the Definition section of this Wikipedia article). The net result of this definition is that vectors behave like little arrows or ordered tuples under addition and scalar multiplication. 
This is good, but often more structure is needed. (See the Vector Spaces with Additional Structure section of the link above.)
For example, a norm can be defined on a vector space. This defines a magnitude or length for each vector. Again there are some rules. No magnitude can be negative. Only the $\vec0$ vector can have a magnitude of $0$. The triangle inequality: $\lvert(a+b)\rvert <= \lvert a\rvert + \lvert b\rvert$
Likewise an inner product can be defined on a vector space. It adds enough structure to support the ideas of orthogonality and projection. For spaces where it makes sense, this leads to the idea of angle. 
The formal definition or a norm is that an inner product is a function that associates two vectors with a number, with some rules. See this for the details. 

These are general definitions which work on all vector spaces. The links above give examples of vector spaces that may not be familiar. E.G. The set of all functions of the form $y = ax^2 + bx + c$ is a 3 dimensional vector space. 
The most familiar vector spaces are N dimensional Euclidian spaces. These are normed vector spaces, where the norm matches the everyday definition of distance. 
The dot product is the inner product on these spaces that matches the everyday definition of orthogonality and angle. See this Wikipedia article.
A: 
How, would I compute their dot product? 

You pretty much have to convert them to the same basis system. You can multiply them out and get nine different terms, and then find the dot product in terms of the nine dot products of the basis vectors, but the math is pretty much the same as converting to the same coordinate system.

In particular, is there a more formal/abstract/generalized definition of the dot product (that would allow me to compute e1→⋅e′1→ without converting the vectors to the same coordinate system)?

The value of  $\vec{e_1} \cdot \vec{e_1'}$  is an empirical value. You can't calculate it simply from a definition.

Even if I did convert the vectors to the same coordinate system, why do we know that the result will be the same if I multiply the components in the primed system versus in the unprimed system?

Given a physical system in which "length" and "angle" are defined, the dot product is invariant under rotations and reflections, i.e. orthonormal transformations. So given two coordinate systems, as long the axes are orthogonal to each other within each coordinate system, and the two coordinate systems have the same origin and the same scale (one unit is the same length, regardless of which direction or coordinate system), dot products will be the same.
In that case, the change of basis can be represented with a matrix $U$ such that $(U^*)U=I$ (For real numbers, $U^*$ is just the transpose, so I'll be using that for the rest, since presumably you're asking about vectors over the real numbers). The dot product of two vectors $x$ and $y$ is $x^Ty$. If $x'=UX$ and $y'=Uy$, then the dot product of $x'$ and $y'$ is $x'^Ty'=(Ux)^TUy=x^TU^TUy=x^TIy=x^Ty$
A: The formula
$$\langle x_1,x_2,x_3\rangle \cdot \langle y_1,y_2,y_3\rangle = x_1 y_1 + x_2 y_2 + x_3 y _3$$
is just a start and, as you go further down in physics, will need quite a few generalizations. The assumptions here are that your vectors are (a) real (b) three-dimensional (c) tuples (d) written in a "standard basis". There are points at which either of these are broken: for example, one of the first things you learn in special theory of relativity(*) is how to work with (b') four-dimensional vectors that (d') don't even allow a standard basis at all, so you get a different formula (of which this is a special case). Similarly, in quantum mechanics, depending on the text, you need to grasp in quantum mechanics are (a') complex vector spaces of (b'') infinite-dimensional things that (c') may not be tuples at all (although often can be written so, again allowing a formula of which this is a special case).
You just yourself figured out that (d) will not always be the case, and that's a splendid job on your part.
Before any of those generalizations take place, the assumptions (a - d) are taken for granted. That is, we are working in a basis
$$e_1 \equiv \langle 1,0,0 \rangle \\
e_2 \equiv \langle 0,1,0 \rangle \\
e_3 \equiv \langle 0,0,1 \rangle$$
and
$$e_1 \cdot e_1 = 1,\ e_1 \cdot e_2 = 0,\ e_1 \cdot e_3 = 0\ \text{etc.}$$
If a triple of numbers is written it is in this basis. While there are other bases, they just represent concrete triples which you have to multiply by the corresponding coefficients and sum up, effectively transforming to $(e_1, e_2, e_3)$, if you insist on applying the scalar product formula above.
The generalization to taking vectors not as triples of numbers, but as combinations of some abstract $e'_1$, $e'_2$, $e'_3$, then requires specifying what $e'_i \cdot e'_j$ is for all $i$, $j$, as other answers have already said in a plenty of ways. If $(e_i)$ and $(e'_i)$ are two different bases, and you know the scalar product in one, the scalar product in the other can be computed from the relations between the basis vectors. And so can a formula for taking scalar products of two vectors, one in each of the two bases.
The basic idea remains, though, and it is a good idea to get oneself familiarized with all the aspects of the above as deeply as possible: to understand the relation between scalar product and norm, orthogonality, expression of geometrical properties and relations (length, angle, distance), etc., before things get too abstract. That's why many texts just hold on to the simplest formula as long as they can.

To actually answer your question: let
$$\vec{x} = x_1 \vec{e_1} + x_2 \vec{e_2} + x_3 \vec{e_3}$$
$$\vec{y} = y_1 \vec{e_1'} + y_2 \vec{e_2'} + y_3 \vec{e_3'}$$
such that $(\vec{e_1}, \vec{e_2}, \vec{e_3})$ is the standard basis.  Let further
$$\vec{e_i'} = \sum_{j=1}^3 E_{i,j} \vec{e_j},$$
so using distributivity and linearity it holds that
$$\vec{e_i'} \cdot \vec{e_k}
= \left( \sum_{j=1}^3 E_{i,j} \vec{e_j} \right) \cdot \vec{e_k}
= \sum_{j=1}^3 E_{i,j} \left( \vec{e_j} \cdot \vec{e_k} \right)
= \sum_{j=1}^3 E_{i,j} \delta_{jk} (**)
= E_{i,k},$$
(also $\vec{e_k} \cdot \vec{e_i'} = E_{i,k}$), so
$$\vec{x} \cdot \vec{y}
= \left( \sum_{i=1}^3 x_i \vec{e_i} \right) \cdot \left( \sum_{j=1}^3 y_j \vec{e_j'} \right)
= \sum_{i=1}^3 \sum_{j=1}^3 x_i y_j \left( \vec{e_i} \cdot \vec{e_j'} \right)
= \sum_{i=1}^3 \sum_{j=1}^3 x_i y_j E_{j,i}.$$
You can use this formula for taking dot products of two vertices in different bases.
I'm not sure if this counts as not converting to the same basis or not: you will need the conversion matrix $(E_{i,j})$ anyway. You won't need to explicitly write $\vec{y}$ in the $(\vec{e_i})$ basis beforehand, though.

(*) Mathematically speaking, special relativity does not use an actual 'scalar product'. But for my example this suffices without further details.
(**) $\delta_{jk}$ is shorthand for "one when $j=k$ and zero otherwise".
