Yes, UDP would work as long as you set up your clients so that they can tolerate out-of-order and dropped packets.
The trick is to set up a UDP "connection" across NAT. There's lots of information about ways to do that:
http://www.google.com/search?q=UDP+across+NAT[
^]
Check them out, not sure about sample code, but these links should give you an idea of what's involved. Then you can decide if it's worth doing or not.