Can two BLE devices communicate?
To answer your question in the title: Yes, two BLE devices can communicate and has been ever since the original 4.0 release.

The change in 4.1 states that a single device can act as both a master and as a slave simultaneously to two different devices. The word for such networks where some devices have a dual role are known as scatternets (will help you googling for more information).

A lot of different BLE to BLE device scenarios are already possible with BT 4.0 single mode (i.e. BLE only) devices. As one commenter said, most devices already support operating as either a master or a slave, either by switching modes or reflashing.

I've used Bluegiga's BLE devices extensively as they were one of the first on the market, don't require buying a compiler and are generally quite beginner friendly to work with. I'd recommend the BLE112 to begin with as it has USB and is relatively easy to solder for an SMD component. You can also easily find breakout boards for it. It is capable of switching between being a master or a slave. The scripting language that runs on their modules, while not as powerful as C, is very quick to work with and prototype use cases.