How do I beat Nasus?

Harass and deny farm. You can also try to bodyblock his Q on a minion by standing on it but it isn't a sure thing. Late game, if he farmed enough, there is not much you can do aside from try to force fights when he is not there and win and out push him.

Another tip is never ever try to duel in his AoE circle. His damage increases quite a bit in there.

Well, before Darius rework, I played darius against him few times, and every time he was 50 stacks at 20 min. So funny killing him, then he TP back just to kill him again. And another strategy I find useful is to leave top lane aroudn 20~25 min. If nasus didn't stack well, he will stay top, while you take their inhibitors

I use 2 strategies against Nasus, either freeze the lane towards your tower. Or push the lane straight into his tower. The tower should kill a bunch of your minions and therefore allow you to cut down on his farm a bit. Never leave him alone in lane for any amount of time. Don't let him free farm at all.
If you need champs to counter him with, google for it. Pretty easy to find out who he is weakest against.

Riven is a very solid counter to nasus. Anyone that can fight without relying soley on auto attacks and has decent mobility is good.