The answer is "we'd do the best we can." No method of teaching language has a perfect 100% success rate.
One common approach that has been suggested in the past is to encode sequences which are very unlikely to occur by chance. For example, there are very few physical processes which can emit a stream of prime numbers, one after another. The idea is that the other species will try many different interpretations of the data, but hopefully the "right" meaning will stand out from the others.
What defines a "good" sequence" is a subject of much debate. This approach is dependent on the other species also finding a sequence meaningful. Some things, such as the series of prime numbers, are thought to be sufficiently fundamental to mathematics that we have a hard time considering languages where they are not given special status. Prime numbers have their roots in Peano arithmetic, which is remarkably fundamental. In fact, they are so fundamental that your particular concern of different bases is not an issue. 13 is a prime number. If they happen to use binary, 1101 is the same prime number. We will encode them differently, of course, but a series of numbers like this is a powerful tool for helping the other side understand the way we think.
Just brainstorming for fun, I could see sending
.. ... ..... ....... ........... ............. on one frequency, with a corresponding decimal or binary sequence on a different frequency (in binary, it might look like
-. -- -.- --- -.-- --.-, using a coding scheme with 2 symbols plus a space symbol). Provide enough correlatable data, and it becomes harder and harder for the aliens to misinterpret the meaning, because false hypotheses get weeded out.