i've tried telling him no in all kinds of ways
What do you mean by this? If you have used any punitive or harsh methods, you are making the problem worse.
With cats, this is NOT a housetraining problem. When cats go outside the box, there is always a reason and we have to find out what it is.
You say he's doing this "all of a sudden". This often indicates a physical problem. The first thing to do is have him checked for a urinary tract problem - very common in male cats.
Are both cats spayed and neutered?
How many litterboxes do you have?
If he checks out fine at the vet, I'll have suggestions for you.