We should form two cases, one of 0 (because 0 can't be the first one) and one with all numbers 1-9, to find out how many numbers there are that use a digit 3 or more times. Then, we can subtract this from 90,000 (the number of five digit numbers). This will give us the desired number.
Case 1: 0 shows up more than 3 times.
When you think about it, the only way 0 shows up more than three times is if the number is 10,000; 20,000; 30,000; etc., up to 90,000. So we just have to add nine to the following case.
Case 2: Some number 1-9 shows up more than 3 times.
This is slightly more tricky. We start with 1, just to make things easy. But when you really start to think about it, 1's would have to fill 4/5 slots in the number for it to break the rules. Therefore, the numbers (if the 5th number is 2) would be as follows:
11112
11121
11211
12111
21111
and we can do the same thing for every other number, 0 and 2-9. However, 01111 does not count, so we have to make sure to get rid of that one as well. Therefore, there are 8 times 5, or 40 ways this can be done for the number 1 for 2-9, and 4 ways this can be done with 0. Overall, the number 1 can be made in 44 different ways. This is also true for 2, 3, 4, 5, 6, 7, 8, and 9 (try plugging them in above where 1 is now). This gives us 9*44 + 9 ways to break the rules, or 9*45 ways. This comes out to 405 ways.
Subtract this from 90,000 and you will see that there are 89,595 ways to accomplish your task.
Say $K(n)$ is the number of such n-digit numbers. Then if 2 is the first digit, the second digit must be 3, and after those two digits there are $n-2$ more digits obeying the same rule, so there are $K(n-2)$ such $n$-digit numbers beginning with $23$. There are $K(n-1)$ such numbers beginning with 3. Thus we get the recursion
$$K(n)=K(n-1)+K(n-2)$$
where $K(1)=2$ and $K(2)=3$. Note the relation to the Fibonacci sequence $F(n)$. We have $K(n)=F(n+1)$, and $K(7)=F(8)=21$.
Best Answer
As you have observed, you cannot have any number ending with a $0$, so your first two digits are fixed.
Division tests for numbers ending with $1,2,5,6$ add no information.
From the division test for $3$, you know that the first two digits must sum to a multiple of $3$.
From the division test for $7$, you know that the number obtained by truncating the last digit and subtracting away twice the last digit from it will give a multiple of $7$. This means that the first two digits have to also be a multiple of $7$.
From these two conditions, the first two digits must be a multiple of $21$, which means they can be $21,42,63,84$.
From the division test for $4$, you know the last two digits must form a number divisible by $4$.
The only one that fits this condition is the first two digits $84$.
So the smallest number is $841$, digit sum $13$.
For rigour, you need to exclude the possibility of the sequence starting with first digit $2$. If this were the case, the final number would end with $9$, and the division test for $9$ demands the sum of the first two digits should also be a multiple of $9$. But this would mean that $63$ is the only possibility, which would conflict with the rule for the last digit $4$ ($34$ is not a multiple of $4$). So we have verified that the above is the only sequence of numbers that meets the criteria.