Sounds like the AMC711x is what you want. You could probably get away without the capacitor in a small battery powered device. If you have long wires between the battery and the driver, you should include the cap to ensure it performs reliably. Otherwise it could oscillate, draw a lot of power, and not give you the output you want. A small 0.1 uF ceramic cap should be fine.
The reason they don't include it in the chip is that even that small value is orders of magnitude larger than what they can put on a silicon wafer of any reasonable size.
I know you want me to define 'long' but I'm not going to. It varies from one part to another, and depends on your layout, battery, and other things. Generally up to a few inches you are okay, possibly quite a bit longer. What you would see if you need the cap but don't have it is that the chip would get hotter than normal. The LED current is likely to be low, but could even be high. If you put an oscilloscope on it you would see the LED current oscillating at a frequency in the tens or hundreds of kiloHertz.
Did you find a good place to buy these? I found lots of datasheets, but no actual parts for sale, except for a couple of questionable listings on eBay.
By the way, I think there's a typo in your first post. It's the 7135 that does 350 mA. The 7113 does 15 mA.