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".