As you probably know the BLE112 is a Bluetooth 4.0 single mode module, meaning it doesn't support/interoperate with Bluetooth devices older than version 4.0. The iPhone 4s and iPhone 5 are pretty much the most popular phones that have Bluetooth 4.0 support and provide APIs to use Bluetooth 4.0. Some android vendors have their own APIs such as Motrola for its Razr phone, but there is no Android API for Bluetooth 4.0. Currently any solution you make is not going to work with just any smartphone with Bluetooth.
Bluetooth 4.0 is also very different to older Bluetooths in the way it transmits and handles data. All data packets are only 20 bytes long. As you have read, at the heart of it is the slave device's (typically a sensor) GATT database which can be through of as a table with keys and values. Compared to the serial port profile (SPP) this is a very different way of thinking of data.
You can read and write the values (attributes) of the keys (attribute handles) locally (sensor / slave) or remotely (mobile phone). The idea with gatt is that instead of you writing your data like name,measurement,timestamp in one long data stream, you update the name attribute ("value"), measurement attribute and timestamp attribute in the sensor's local gatt. These changes then gets indicated to the mobile phone over the air. In short: Bluetooth 4.0 is not intended to be used for creating a data stream.
However, it is always possible to simulate or emulate streaming even when everything is packetized. Bluegiga provides a "Bluetooth Smart: Cable replacement application note" (registration required) which discusses exactly how to replace a UART cable with Bluetooth 4.0 and they give detailed explanations of how to accomplish that with the BLE112.
Update: Any device with Bluetooth and an Android version 4.3 or newer supports Bluetooth 4.0 natively. All the old vendor specific stacks have been deprecated in favor of the official support.
The advertisement packet your beacons send can contain custom data. However the space is very limited, around 31 bytes. About 16bytes of it goes to the 128bit "service UUID" of your beacon. The structure of the packet is defined by the bluetooth spec and it does have some overhead, so I'm not sure how much is actually available for the custom data.
The service UUID is an identifier which your iphone app will search for. The idea that each service has a unique identifier, so if an app wants to find heart rate monitors, it will scan for the heart rate monitor uuid. In iOS you can even do a wildcard scan, and it will return any ble advertisements it can find, regardless of the services it has. It is however recommended by Apple guidelines that you specify the service UUID.
There is no requirement for pairing in order to receive the advertisment packets from the beacon. There is also no theoretical limit that would prevent that the beacons couldn't be found, given an infinite amount of time.
I haven't heard anyone putting 500 advertising BLE beacons in the range of an iPhone to see how many it can detect. With 500 beacons advertising simultaneously there will be a lot of collisions between packets. This could theoretically be calculated with knowing the advertisement interval.
The iPhone scan window (how long the channels are actively listened to) and scan interval (how often the scanning window is entered) cannot be adjusted, isn't documented and cannot be relied to remain the same between versions. This means that there isn't a way to really calculate how the advertisements will be found.
There's some recommendations published by Apple about advertising: https://developer.apple.com/hardwaredrivers/BluetoothDesignGuidelines.pdf
Oh, and by default iOS will filter the results so you get one notification per scan session, per beacon. You can set the "allow duplicates" option in the scan to get multiple notifications per scan session for each beacon if this is needed, but again, apple doesn't recommend it.
If you end up testing this with 500 beacons, or even > 10, I thin a lot of people would be interested in your results. I personally would also appreciate hearing about your experiences.
Best Answer
The BLE Chip that was used, uses the Serial communication to send the data to the µC. In this case it produces some overhead for the chip. The problem was solved by 4. option using the another BLE chip with SoftDevice on the emedded µC. So there no more serial communication needed and the scanning and procesing happens in a single chip.