For an integer to be divisible by 3, the sum of its digits must be divisible by
3.

Case 1.  The number has 5 digits.  

Then it will be divisible by 3 because 3+4+5+6+0=18, which is divisible by 3.

All 5 digit numbers are greater than 5000, so

We choose the 1st digit 4 ways. (The first digit cannot be 0)
We choose the 2nd digit 4 ways.
We choose the 3rd digit 3 ways.
We choose the 4th digit 2 ways.
We choose the 5th digit 1 way.

So there are 4∙4∙3∙2∙1 = 96 five-digit numbers.

Case 2. The number has 4-digits and does not contain 0 as a digit.

Then it must be an arrangement of 3,4,5,6.  Any such arrangement is divisible by
3 because 3+4+5+6 = 18.

Since it must be greater than 5000 there are only 2 choices for its first digit,
5 and 6.

We can choose the first digit 2 ways.
We can choose the second digit 3 ways.
We can choose the third digit 2 ways.
We can choose the fourth digit 1 way.

So there are 2∙3∙2∙1 = 12 ways for case 1

Case 3. The number has 4-digits and contains 0 as a digit.

Then the other 3 digits besides 0, must have a sum which is divisible by 3,
since the 0 will not change the sum of the digits.

So the other three digits must be 3,4,5 or 4,5,6, because 3+4+5=12, which
is divisible by 3, and 4+5+6=15, which is also divisible by 3. 
[Note: The only other two combinations of digits 3,4,6 and 3,5,6 do not have 
sums divisible by 3.]

Sub-Case 3A:  Its digits are 3,4,5,0

We can choose the 1st digit 1 way, (as 5).
We can choose the 2nd digit 3 ways.
We can choose the 3rd digit 2 ways. 
We can choose the 4th digit 1 way.

That's 1∙3∙2∙1 = 6 ways.

Sub-Case 3B:  Its digits are 4,5,6,0

We can choose the 1st digit 2 ways, (as 5 or 6).
We can choose the 2nd digit 3 ways.
We can choose the 3rd digit 2 ways. 
We can choose the 4th digit 1 way.

That's 2∙3∙2∙1 = 12 ways.

Answer: Adding all numbers for all the cases and sub-cases:

96+12+6+12 = 126 integers.

Edwin