Counting by perfect 5ths allows us to construct the entire 12 scales and their relative majors/minors but can we count by any other intervals and still be able to construct a complete scale?

Yes, we know we can make a complete Circle of 5ths and we can also make a Circle of 4ths. All we need to do is follow the order of the 5ths in reverse since perfect 4ths are merely perfect 5ths inverted and vice-versa. Both circles are mirror images but otherwise identical. Can we make complete circles of other intervals? Yes, we can. We can make a complete circle of minor 2nds. Since a minor 2nd is a half-step, of course we can travel around the circle in half-steps since there are twelve of them. So, logically, we should be able to take the inverse of the minor 2nd and make a circle of it too. And we can. The reciprocal of the minor 2nd is the major 7th (eleven half-steps from the tonic) and it too ends up tracing out the circle semitone by semitone.

Can we make a circle with major 3rds?

No. We eventually begin repeating scales without naming all twelve. This happens with any intervals other than the 4th, 5th, half-step and major 7th. Why? Because a 4th is 5 half-steps, a 5th is 7 half-steps, a minor second is 1 half-step and a major 7th is 11 half-steps, and the octave is 12 half-steps. 1, 5, 7 and 11 are what we say in mathematical jargon co-prime in modulo 12. That is, they are not divisible with any number other than 1 and themselves and also share no factors with 12. All the other intervals are not prime or are factors of 12 or both and so end up creating circles that are factors of 12 but never all 12.