EDIT:Thanks to TheGamingLemonfor giving me a little shoutout in the description of his video. Make sure you check him out for more Minecraft tips and tricks!
If anyone finds stal please comment telling me where you found it. (You will recieve credit for the find)
NEW GUIDE (TU7)
where are we now - (X: 373 Y: 65 Z: -146) On an island On the east border of the map. [Also contains Pickaxe] strad - (X: 27 Y: 85 Z: 84) Up in tree to the right of the castle. [Also contains Iron Axe with Fortune III] cat - (X: -42 Y: 57 Z: 249) In a cabin to the left of the castle. [Also contains Iron Boots with Feather Falling IV] 11 - (X: 103 Y: 81 Z: 166) On top of the border of the castle. [Also contains Bow with Power V] 13 - (X: 107 Y: 75 Z: 165) In the tunnel exiting the tutorial. [Also contains Jukebox, Bow with Flame I, and 20 Arrows] ward - (X: 48 Y: 80 Z: 182) In the castle library on top of some bookshelves in the back. [Also contains Iron Pickaxe with Unbreaking III] chirp - (X: 42 Y: 77 Z: 153) Behind the lavafall in the castle enchanting room. [Also contains Iron Chestplate with Fire Protection V] mellohi - (X: 64 Y: 83 Z: 181) In the upstairs right bedroom behind the painting. [Also contains Iron Sword with Smite V] mall - (X: 102 Y: 60 Z: 268) To the left of the castle take the train to the sand temple. [Steping on the pressure plate gives Iron Sword with Looting III] blocks - (X: 65 Y: 71 Z: 176) In the basement of the house passed the lava moat. [Also contains Iron Helmet with Respiration III] far - (X: -46 Y: 64 Z: 249) Behind the cabin attached to the chimney. [Also contains Iron Shovel with Effiiciency V] Thanks to mihaeagle3 for finding this one.
1.8.2 (TU6) Guide:
Thanks to everyone for all the help and I hope you enjoy this complete guide to finding all the music discs. Have a great day
ATTENTION: IN ORDER TO FIND EVERY CHEST YOU SHOULD NOT EXIT THE GAME.
13 - when you spawn, head out of the miners cave, In this chest is the music disc, 13 along with a jukebox, 20 arrows and a bow. (-132, 67, -47)
cat - after exiting the cave, turn around and look up. On both your left and right, you should see 2 windows. Climb up to the window on the right and break it. Inside is a chest containing cat and a stone sword. (-134, 71, -45)
strad - before you cross the minecart bridge, look up. In the "A" in "Minecraft" on the side of the village is a chest. You will need aprox. 25 blocks to get high enough to reach it. There is also full diamond armor in this chest. (-147, 91, -33)
chirp - in the middle of the village is a well, sinking down this well will reveal a secret room containing a chest holding chirp and full gold armor. (-194, 57, -36)
11 - at the far end of the village is a farm, next to the farm is a watchtower, climing to the top of this watchtower will reward you with a chest containing a diamond shovel and the music disc, 11 (-189, 76, -39)
far - back at the starting location after you exit the miners cave, head to your right. You should see another village with a blue flag at the top. In the chest at the top of that tower is a iron sword and the music disc, far(-152, 80, -230) (Thanks to ABCZ for this one)
blocks - behind the starting area is a cave with a coblestone brige generator in front. When you enter the cave, head to your right at the intersection. In this room head up the stairs, there should be a chest by the bed containing full iron armor and the music disc, blocks(11, 90, -22)
ward - from the entrance to the cave, head to the left and around the corner, in the doorway on the right is a chest containing another diamond shovel and the music disc, ward.* (36, 83,-60)
stal - exit the cave and head to your right. Climb up the hill before you, after reaching the very top you should see a lone tree, near this tree is an overhang with a chest on it. This chest contains a diamond sword and the music disc stal (40, 115, -100)
mellohi - from the location of stal, look to your right, you should see a woonden platform on top of a large tree, at the bottom of this tree is a ladder, the chest is here. It also contains a diamond axe.** (170, 94, -164) (Thanks to ABCZ for this one)
mall - buckle up, because this one is quite the journey. From the last location, head south, (the minecraft logo should be on your right side). When you reach a desert, you should see a red flag off to the right. Again, in the tower the flag is perched on, is the disc.**(94, 75, 295)
where are we now - outside of the town you found the previous disc in, is a dock with a sigle boat in the water. In front of you is an island. Jump in the boat and head for the island. Upon ariving, jump for joy at having found the final music disc.**(267, 65, 331)
*Also located on the ceiling of this room is a switch to open the nether portal on the far wall. **This is one of the discs that cannot be found if you exit the map.
EDIT 1: Spelling errors.
EDIT 2: Added 2 more locations.
EDIT 3: Changed colors and added citations.
EDIT 4: Added another location.
EDIT 5: Added the final location.
EDIT 6: Added cordinates
EDIT 7: Added new guide as of TU7 update