dhclient blues

I hope someone here can give me a pointer to a solution
because this has me ripping my hair.

There is a hole in the wall that brings internet connectivity
and IP addresses assigned by DHCP. No modem or anything, just
an ethernet plug. I am entitled to 5 IPs, which are assigned
to me at random and non-consecutively anywhere within a random
/26. As long as I put a switch on the wall and connect machines
to it, I have no problems.

However, I want a firewall between myself and the net. This
means a box with two interfaces, say eth0 to the ISP and
eth1 to the LAN. The machines on the LAN must, for various
reasons, remain on public IP space. Thus, NAT is ruled out.

And here comes trouble. eth0 on the firewall gets an IP from
the ISP alright. I have dhcrelay running, so the machines on
the LAN can also get their IPs from the ISP as soon as eth1
on the firewall is up. But how do I get an IP for eth1?

If I configure eth1 for dhcp, it sends its requests out on
the LAN, which is pretty useless. At the same time I can't
configure it statically because I don't have a contiguous
subnet, so whatever IP I could take at random from the
random /26 I happen to be part of, might be assigned to
someone else. And dhcrelay will relay *through* the machine,
but not *on* it.

Any ideas anyone how I could get eth1 to send its dhcp
requests out through eth0? Or how I could get eth0 to request
an extra IP and then route it through to eth1?

Z