Is there an online algorithm for radix conversion?
This answer is not complete, but it is the start of a complete answer, and nothing else has been offered.  I hope to finish it another time.

I have found that an online right-to-left algorithm exists in a more general case than I mentioned in my original question.



I suspect that no such algorithm exists in general, for reasons I outlined in my comment.  What would the online algorithm produce first?

Units digit first

Suppose the algorithm wants to produce the units digit of $Q$ without reading all of $P$.  Represent $n$ in base-$p$ as $n = \sum_i d_ip^i$ where each base-$p$ digit $d_i$ is between $0$ and $p-1$ inclusive. The units digit of $Q$ is equal to $n\bmod q$ which is $$\Bigl(\sum_i d_ip^i\Bigr)\bmod q.\tag{$\star$}$$  The result depends on every one of the $d_i$ unless the corresponding term $d_ip^i$ has the same value $\bmod q$ for each possible value of $d_i$.  In particular we must have $$0\cdot p^i \equiv 1\cdot p^i\pmod q$$ so $p^i$ must be a multiple of $q$ in order for us to ignore the $i$th term of the sum.  Say $p^{k_0}$ is a multiple of $q$ for some $k_0$.  Then in computing the units digit of $Q$ we can disregard all the terms of the sum with $i\ge k_0$, and we need only examine the first $k_0$ digits of $P$.

To compute the next digit of $Q$ we can disregard all the terms of the sum with $i\ge k_1$ where $k_1$ is the smallest number for which $p^{k_1}$ is a multiple of $q^2$, and so on.

For example, suppose $p=6$ and $q=8$ and $n=3021213_6$.  $6^3$ is a multiple of $8$ so we can generate the units digit of  $Q$ just by examining the last three digits of $P$.  $2\cdot6^2 + 1\cdot 6 +3 \equiv 1\pmod 8$ so the units digit of $Q$ is 1.   Reading the next three digits of $P$ will allow us to compute another digit of $Q$, and so on.

This situation includes the case of $p^i=q^j$ that I discussed in the original question, but it is more general.

Note that although the $k_i = O(i)$ it may not increase smoothly.  We actually have $k_i = \lfloor c(i+1)\rfloor$ for some rational constant $c$ that depends on $P$ and $Q$.  For example, $24$ is a multiple of $4$, and so $24^2$ must be a multiple of $4^2$, but it is also a multiple of $4^3$.  Next $24^3$ is a multiple of $4^4$ but not of $4^5$.  So when converting from base $24$ to base $4$, reading the first digit of $P$ gets you one digit of $Q$, but reading the next digit of $P$ gets you not one but two more digits of $Q$. Reading the third digit of $P$ gets you only one more digit of $Q$.  Here $c = \frac32$. 





(To come: most significant digit first; intermediate digits first.)