In different versions of Minecraft there have been various exploits that allowed a player to break/replace unbreakable blocks in survival.
Headless pistons (current) Edit
There are methods to get headless pistons in survival. Normal headless pistons have the property, that they delete the block directly in front of them when they retract. This can be used to break bedrock.
The main problem with this method is, that while it is easy to first make a headless piston and then place a bedrock block in front of it (in creative mode or using some other obscure survival firendly method ), it is very difficult to have a naturally generated bedrock block, and then make a normal headless piston face into that bedrock block. It is however possible. (And the description of that is TODO)
Dragon Egg (current) Edit
 Gravity affected Blocks in lazy-Chunks by RedstoneSpire
Gravity affected blocks have a different behavior in non-entity-processing chunks than in entity-processing chunks. Due to a bug in the dragon egg code, dragon eggs in non-entity-processing chunks will delete any block they fall on in non-entity-processing chunks. This can be used to delete bedrock.
Here´s a video demonstrating this: https://youtu.be/j33vAgJdDrQ
A more in-depth description of this is TODO.
Ender Crystals (current) Edit
How to keep the old Endportal by Panda4994
This only works in The End, because that is where ender crystals generate fire.
We push the ender crystal into bedrock when it is in lazy chunks, so it doesn't explode (as it doesn't get ticked). When it's inside the bedrock we make the chunk an entity processing chunk again and it places the fire which "breaks"/replaces the bedrock.
This video by Panda4994 also explains how to keep the old end portal in 1.9 and how to spawn the new portal at a desired Y-level, which is as cool as breaking bedrock, too.
Nether Portals (current) Edit
By removing all valid locations, except for a certain spot, where nether portals can generate, it is possible to force the portal to generate in that location. This deletes the blocks the portal forms on.
Dark Oak Saplings (1.7 - 1.8.1) Edit
This was probably the most widely used method for breaking bedrock. By planting dark oak saplings under some logs (of any type and orientation) causes some variants of the dark oak trees to grow with the top of the tree at the level of the saplings. The trunk of the tree may puncture through any blocks except for the centre 2x2 area that contained the saplings.
Beds (1.8.1 only) Edit
In 1.8.1 it was possible to place a bed on top of the hitbox of a Dead Bush, Grass, Fern or Vines. The front half of the bed would replace whatever block it occupied.
Skulls and Chests (1.7.9 only) Edit
In 1.7.9 it was possible to place skulls on the side of a chest. The skull would replace whatever block it occupied.
This worked with any type of skull, however in 1.7.9 you could only get a wither skeleton skull in survival.
Arrows and TNT (up to 1.7.5) Edit
Before 1.7.5, and in older snapshot versions of 1.8, arrows would remember the location of the block that they were stuck in. When the block, that a flaming arrow was stuck in, was quickly broken and replaced by TNT, then when the arrow hit another block it would replace that block with ignited TNT.
(Needs more detail.)
It was also possible to change block data values with this bug.
basically the arrow remembered the coordinates of the block it was last on, for it's calculations. in the scenario sited above, the arrow would land and check what's in those coordinates. it would see the tnt, and since flaming arrows ignite tnt, it would change the block it fell on (thinking it was TNT) into a PrimedTNT entity. also, if you for example had the block it remembered be a cauldron, it could change block IDs. this is because cauldrons lose water when a flaming arrow gets into it, therefore changing it's block ID. when the arrow fell, it thought it was changing the block ID of the cauldron, but in reality it changed the block ID under itself.
Pistons (up to 1.7.5) Edit
 Description is TODO!
Pistons (up to 1.0.0) Edit
Soon after the release of Minecraft 1.0.0 a user who goes by the name of Spanone discovered a bug which iluminated what can really be done with redstone. The very first Block Metadata Changer. At first s/he noticed it turned logs into other variants of log. However it soon became apparent that you could do much more with this little glitch (e.g. creating invisible, non-collideable, pushable blocks). Read More
The first design, to remove bedrock, was discovered by Regular Hexahedron.
I just invented a way to destroy bedrock with pistons. And obsidian. And apparently any block, but it's bedrock/obsidian that should excite you.A contraption was later built by WubbiConcepts .
Try using the machine to create a piston with data value 13. If you consult the water placement chart that's the same as dark green wool.
The piston will be rotated east, and also extend extremely briefly. Any block it extends into is deleted without a trace. Including bedrock/obsidian.
It can also delete containers immune to pistons like chests and dispensers. When it does this their contents are spilled, rather than being deleted with the container.
Sticky pistons and regular pistons both work in the deleter.
EDIT: And piston data value #12 seems to be a west facing deleter
Mushrooms (Alpha/Beta) Edit
From the Minecraft Wiki Bedrock Talk Archive_1
Mushrooms can be planted anywhere but if you use bonemeal on a mushroom the block turns into dirt; ultimately detroying the bedrock layer with mushrooms and bonemeal NOT TNT Killrbladez 15:22, 20 November 2011
Pistons (up to ??) Edit
In the early days of the official Minecraft release it was possible to break bedrock with bud pistons.
Need research, I think the ZipKrowd guys have a video about this.
Hoes (up to Alpha/Beta ??) Edit
In the early days of Minecraft you could just remove bedrock by placing and hoeing a dirt under it, then planting crops on it.