Almost all logarithms of almost all numbers in almost all bases are in fact irrational. When you say you don't want an approximation, how do you plan to write down these irrational numbers exactly? (By the way, the same goes for square roots: there's an algorithm for them, but for almost all inputs, computing the output exactly requires infinitely many steps.) If you're willing to allow infinitely many steps, then the Taylor series (with a little preliminary work) will do fine.
Here's a solution for when then base $b$ is bigger than $1$; I leave the other case to you.
The preliminary work is this: take your input (positive) number $x$. If it's between $1$ (inclusive) and $2$ (exclusive), write down $0$, and move on to the real work below, renaming your number $x''$.
Otherwise, if it's less than $1$, multiply $x$ by $b$ until you get a number $x'$ that's between $1$ (inclusive) and $b$ (exclusive). If you multiplied by $b$ some number, $k$, times, write down $-k$.
$$
\log_b(x) = \log_b(x') + \log_b(b^{-k} = \log_b(x') -k
$$
so all you need to do is compute $\log_b(x')$. A similar approach works for numbers larger than $b$.
So...after some number of multiplications/divisions by $k$, you get to a number $x'$ between $1$ and $k$. If $1 \le x' < 2$, move on; otherwise, compute the square root, and get that
$$
\log_b(x') =2 \log_b \sqrt{x'},
$$
so you only need to compute the log of that square root. Repeatedly extract square roots until you get a number less than $2$, call it $x''$. Move on to the "real work" portion.
If $x$ is bigger than $b$, divide $x$ by $b$ until you get a number $x'$ that's between $1$ and $b$ as above. If you divided $k$ times, write down $+k$, and use this to show how $\log x'$ is related to $\log x$. Then use square roots, as before, to reduce to a number between $1$ and $2$, and call that $x''$.
The "real work": Now use the Taylor series (for $\log$, of course!) to compute $p = \log x''$; that'll take infinitely long in general, but you already indicated by your willingness to extract square roots that this was OK.
Your final answer for $\log x$ is $\frac{p}{\log b}$ plus the adjustments from the preliminary phases. Of course, this requires that you compute $\log b$... which you can do using the second phase (to reduce $b$ to a number smaller than $2$) and the third (using the Taylor series).
Thanks to @DavidK for pointing out that in an earlier version I was assuming convergence of the series for $\log_b$ on $1 \le u < b$, when I should only have used $1 \le b < 2$.
Note too, that if you like square roots, you can skip the first phase and just take square roots for longer (at least if $x$ starts out larger than $b$).
====
I don't claim any efficiency here. You win BIG by dividing/multiplying at least once more by $\sqrt{b}$, and then adding/subtracting $\frac12$ from the result, because convergence of the Taylor series is a LOT faster when you're in the first half of the domain of convergence.
N.B.: For an arbitrary input $x$ and base $b$, even expressing these numbers is likely to take infinitely long.