Let's call a string of digits "good" (as in good to go) if it ends in a digit between $1$ and $8$, and "bad" if it ends in a $0$ or $9$. Let's let $g(n)$ and $b(n)$ count the number of good and bad strings of $n$ digits that don't have any adjacent pairs $09$ or $90$. It's easy to see that
$$\begin{align}
g(n+1)&=8g(n)+8b(n)\\
b(n+1)&=2g(n)+b(n)\\
\end{align}$$
It follows that
$$\pmatrix{g(n)\\b(n)}=\pmatrix{8&8\\2&1}^n\pmatrix{1\\0}$$
The probability that the OP seeks is $p(n)=(g(n)+b(n))/10^n$, or
$$p(n)={1\over10^n}\pmatrix{1&1}\pmatrix{8&8\\2&1}^n\pmatrix{1\\0}$$
An exact formula analogous to the Binet formula for Fibonacci numbers can be obtained by diagonalizing the $2\times2$ matrix. However, the eigenvalues here are
$$\lambda={9\pm\sqrt{113}\over2}$$
so the analogous result is likely to look a little ugly.
Your computation of "with replacement" has a bit of a problem, in that you're assuming that there are $10^4$ possibilities -- but $1000$ of those are not actually possibilities, because you're explicitly specifying that the first digit cannot be $0$.
A shorter computation: "With replacement" the possible numbers are $1000$ through $9999$, and all of these $9000$ numbers are equally probable. Every fourth of them is divisible by $4$ -- no need to consider digits here, just notice that the interval from $1000$ to $9999$ contains a whole number of four-periods.
So the probability in this case should be $\dfrac14$.
Without replacement, imagine choosing the two last digits first, which can be done in $90$ ways. How you choose the two remaining digits is then immaterial.
How many endings from 00 to 99 are divisible by 4 and don't repeat digits? All the 25 you know, except for 00, 44, and 88.
Actually, that may not work. We run into the problem that it is not even well-defined what it means to choose the four digits "without replacement" when the leftmost of them cannot be $0$.
We can see this clearer if we imagine choosing two digits "without replacement", where the left one must not be $0$.
If we choose the left digit first (and that is not $0$), there will be nine digit to choose from for the right digit, and $0$ is always among them -- so the probability of the right digit being $0$ is $\frac19$. On the other hand, if the choose the right digit first, all ten digits will be available at that time, so now the probability of the right digit being $0$ is only $\frac1{10}$.
You need to specify which order the digits are picked in, if you want "without replacement" at the same time as "leftmost digit must be nonzero". Otherwise it is ambiguous what the probability of picking each particular number is.
Of course you can also specify that you're choosing uniformly in a single step between all sequences of 4 diferent digits that do not start with $0$. But it seems to be hard to argue that "without replacment" is an accurate description of that procedure.
Best Answer
There are $10$ choices for the digit that appears twice and then $9$ choices for the digit that appears once. There are $\binom{3}{1}=3$ ways to arrange the digits. This gives $10\cdot9\cdot3=270$ choices out of $1000$. That is, a $0.27$ probability.