Whenever you see that something that should work isn't working, you need to ask if there is some other factor involved that you are not seeing. The rule

sudo iptables -A INPUT -p tcp ! --dport 8080 -j REJECT

Looks like it should work, but you have appended it to the INPUT chain, so it is probably circumvented by a previous rule in the chain. This rule should be adequate by itself, as the INPUT chain is the first chain that incoming packets hit. If they are REJECTed at the INPUT chain, they never get to the FORWARD or OUTPUT chains. Of course, this rule will block everything TCP that is not destined for port 8080, which is probably not what you really want in the end unless the proxy at 8080 is the only service on the machine and you only log in from the console.

So the first thing to do is to list the rules and look for what might be causing the packets to pass:

sudo iptables -L

If your firewall is reverse NATting then you should also list the NAT table.

sudo iptables -L -t nat

Afterwards, try the putting the same rule at the beginning of the chain:

sudo iptables -I INPUT -p tcp ! --dport 8080 -j REJECT

and see if that doesn't solve the problem, or at least give you more confidence that you understand how iptables works so that you can complete your rule set. If you are working on this host from remote, my suggestion will cut you off, so you should do this only from the console. To work safely from remote see my colleague Eli Rosencruft's post about tweaking firewalls from remote.

First read a bit of iptables documentation - specifically you at least need to know what chains in what tables a packet will enter (take a look here: http://www.iptables.info/en/structure-of-iptables.html).

You'll have to balance between two things: your goal to force everyone to use proxy and everybody's convenience. On one hand you can disallow forwarding of any packets at all (you can even disable ip_forwarding flag in the kernel). This way local computers will be able to access the internet only by your proxy server. But even that won't stop everyone from using a tunneled connection through your http proxy (and it's even easier with https ones). So you won't be able to fully monitor or limit internet usage.

On the other hand you can take an even softer approach: just limit outgoing traffic to port 80. In that case the software which doesn't use http (e.g. skype) won't have to tunnel traffic in http and the good-behaving clients will have all the benefits of a local http cache (faster access to sites).

Your current configuration looks like the first option above. But you have the unnecessary ACCEPTing rules in FORWARD chain. You don't want the router to forward any packets. Local computers connect to your proxy (packets go through INPUT chain) and not to the remote hosts. With your current setup someone could find a proxy listening on port 8080 anywhere on the internet and use that instead of your proxy.

If you don't want your clients just accessing http{s} sites without the proxy, than you may just DROP or REJECT forwarded packets to ports 80 and 443:

IPTABLES -I FORWARD -i eth1 -p tcp -m multiport --dports 80,443 -j REJECT

Where eth1 is your internal interface. Doing this way you won't have to mess around with other ports/access.

Standard

A separate (user-defined) chain might help.

# create a chain just for user 100 (192.168.1.100)
iptables -N custom_user_100

# redirect all traffic FROM user 100 to custom chain
iptables -A INPUT -p tcp -s 192.168.1.100 -j custom_user_100

# return from user chain for valid traffic, drop all other
iptables -A custom_user_100 -p tcp --dport 8080 -j RETURN
iptables -A custom_user_100 -j DROP

So - what this does is redirect any traffic FROM 192.168.1.100 into a custom chain. This custom (user-defined) chain merely returns if a valid match is found (traffic destined for port 8080). All other non-matching traffic that doesn't result in a return from the chain is dropped.

Later you can view the tables statistics to verify this is what happened:

iptables -L -v -n

Forwarding

Now, on the off-chance you are processing forwarding traffic, there will be a different set of rules - but the idea of using a custom (user-defined) chain is the same. I like to refer to the diagram at this link: http://www.csie.ntu.edu.tw/~b93070/CNL/v4.0/CNLv4.0.files/Page697.htm when trying to understand the flow of packets.

In this case you might want to do something like the following:

# create a chain just for user 100 (192.168.1.100)
iptables -N custom_user_100

# redirect all traffic FROM user 100 to custom chain
iptables -A FORWARD -p tcp -s 192.168.1.100 -j custom_user_100

# return from user chain for valid traffic, drop all other
iptables -A custom_user_100 -p tcp --dport 8080 -j RETURN
iptables -A custom_user_100 -j DROP

This is identical to the first except that the rule that was applied to the INPUT chain is, instead, applied to the FORWARD chain.

Update 2013-05-24

I've re-read your question. So will start over.

Let's assume your "proxy" is actually a router. That is - it is passing all packets from one interface to another - perhaps using NAT. This means that all packets of interest are flowing through the FORWARD chain.

Next: you say you will configure all clients using port 8080 to hit the proxy itself. Fine. This means that all those packets will enter the "proxy" via the INPUT chain.

So: you just want to prevent anybody from going out port 8080 on the FORWARD chain.

iptables -A FORWARD -p tcp --dport 8080 -j REJECT

This rule will ensure anything that is to be forwarded to a destination port of 8080 will be rejected (an ICMP packet will be sent to the client that attempted to pass the packet through the proxy).

After you implement this rule it is VITAL that you test this by attempting to make such an forbidden connection - then you list the rules by typing:

iptables -L -v -n |grep 8080

and ensure the counter has increased. If not then something is wrong with the router configuration.

Personally, I like to set the default policies for the INPUT and FORWARD chain to DROP

iptables -P INOUT DROP
iptables -P FORWARD DROP

Then allow only the traffic I want - this way, I find less surprises and am very certain only what I allow is going where I direct it.