Is NAT not a routing protocol? It certainly seems so to me -- you dynamically change your packet destinations, error behavior, and even their contents based on dynamic state detected from the network.

But yes, you mean OSPF et. al. Yes, you can certainly run those on a wifi router (they don't from the factory, so reflash with dd-wrt or whatever). Machines much less powerful were doing dynamic routing using these protocols 20 years ago.

It runs static routes just fine ;-) You can bake in quagga using their SDK if you want OSPF etc.