Pre-paired bluetooth chips
No, I don't see how that would work.  Certainly the manufacturer is not going to be selling Bluetooth chips in pairs (how would they be stocked?), and neither would a distributor like Digi-Key or Mouser do this sort of thing (think special hardware jigs, software etc.).  You might get a third party to do this for you at a price, depending on volume.

You have to allow a device to be paired to use it in a secure mode.  This pairing is done by exchanging MAC ID's (like serial numbers) between the two devices, which are then stored by both chips.  This what allows the chips to connect again later without have to be paired again.

Essentially, to have two chips "pre-paired", you have to have both chips available, run firmware on each side to perform the pairing, and then sell them together as a product.  Since they both have their respective MAC IDs stored, that will continue to work after the consumer receives them.  For example, I have seen this dongle which is advertised as being pre-paired.

It is possible to pair without having to use a PIN number (or use a trivial one like 0000, which can be preprogrammed into the firmware).  Pairing still has to be initiated though.

This SE question deals with communication without pairing a Bluetooth device, but you have to have access to both Bluetooth chips to make the necessary changes to chnage the friendly name.

Also, I believe the latest Bluetooth 4.0 spec has a means of communicating without pairing, but it is not secure.