Actually I think everything you want to do can be done with the wireless devices themselves. I know something very similar to what you want to do is being done in a lot of places. I don't think you would even need a separate Linux box. You would just configure the DHCP on the wireless device to hand out addresses in the public range and have them point to the Cisco Router for their gateway.
In fact at home I have my wireless access point configured to act as a wireless->Ethernet bridge. I don't even use the WAN interface on the wireless unit. The unit has a 5 port switch that is bridged with the WLAN interface. I have one of the ports on the switch plugged into my normal wired LAN and I have a Linux machine that acts as my DHCP/DNS server on that LAN. When my laptop associates with the access point it picks up it's IP address from my Linux DHCP server and points to my Linux gateway (which in your case would be the Cisco router). You could do a similar thing except your DHCP server would be configured to hand out addresses in your public range rather than private addresses like I am doing. The access point itself can do the DHCP and it's probably better that it does. If you wanted to be geeky you could even get an access point that runs Linux like the one I run and customize it to do whatever you want (it runs iptables, dhcpd, etc).
I would suggest two other places to post for advice where I also frequent:
http://openwrt.ksilebo.net/forum/
http://www.sveasoft.com/modules/phpBB2/
Of course these mainly deal with the LinkSys unit like I run at home (and a few devices with the same chipsets). These are running Linux. Another great wireless resource:
http://www.seattlewireless.net/
Of course here's a web server running on one of my home access points:
http://voidmain.is-a-geek.net:81/
:) So yes, I think what you want to do is very doable. I would just check around for other people who are doing something similar and see how they are doing it. You could use the MAC filtering built in to the wireless unit to restrict access. This would probably not be the best way to do it though. Having some sort of enctyption with individual keys would be the best method (IPSec based would be the most secure). I've done a little war driving and it's quite amazing how insecure most wireless systems are.
EDIT: Forgot to address your 4-mile with no line of site question. I don't know how you would do that other than get some really tall antennae. We had a 10 mile line of site (from the top of a 25 story building).
Also, for long distances you are going to need a directional antennae on both ends. How is this going to work on a boat? I certainly won't admit to being a wireless expert (because I am not) so there may be ways I am not aware of. Of course you could strategically place a few access points in the harbor and use regular omnidirectional. You could then have one directional between the harbor and the main office with the router. I don't know what you would do for boats out on the water (not docked) if you were even worried about them. I know they run Satellite receivers on airliners now so they could probably do satellite connections on boats as well which would give them unlimited range. I suspect that would be very expensive though.