実際に構築したことはありませんが、
udhcpdパッケージを導入し、
http://packages.ubuntu.com/lucid/udhcpd

http://manpages.ubuntu.com/manpages/dapper/man5/udhcpd.conf.5.html
http://manpages.ubuntu.com/manpages/hardy/man8/udhcpd.8.html
http://open-wrt.ru/forum/viewtopic.php?id=162
あたりを参照して設定すればできるかと思います。
もしかするとiptablesの設定が必要かも知れません(もしかしたらシステム側がよきに計らってくれるのかも知れません)。

ただ、苦労してPCを使って構築するよりも、手間や消費電力や機材費などを考えると、安くても最低限の機能を備えたルータを買ってきたほうが簡単で手っ取り早いかと思います。

趣味や興味でやるのならば、問題無しですが、なにかしらかの制限、課題があるのであれば、手段ではなく、問題としていることを投稿いただけると、何かよりよい対案についてコメントが付くかも知れません。

ルータは要求仕様次第なのでなにがお勧めとも言い難いです。
私は使用している、
http://121ware.com/product/atermstation/product/warpstar/wr1200h/spec.html
は、MACアドレスで固定IPを割り当てる機能が無いようです。
https://121ware.com/aterm/regist/qa/qa/00010.asp
あたりを見て、できるものを選ぶというのはいかがでしょう。

# なぜNECかというと、仕様一覧表にLinux対応と書いてあるので。
# 他社のルータでも問題無いですが、*わざわざ*Linux対応と書いている姿勢に敬意を表してATermシリーズを買っています。 :D

ちなみに私のルータはMAX5Wです。最大電力で回し続けても2円/day程度です。60円/month、720円/year程度です。
PCの場合は、少なくともこの10倍はかかるかと思います。