Did you set a bed? If so, dying will take you to that bed.
You said you tried using a map. Did you zoom out that map fully to zoom step 4? If not, it's worth a try. A zoom step 0 map covers 128 X 128 blocks, a zoom step 4 map covers 2048 X 2048 blocks.
If these don't work, my recommendation is MCEdit. MCEdit is an external program which can open and search world files.
- Open MCEdit
- Select your world in the left menu
- Click Edit button
- On the right will be a large graphic output. At the top of it is 3 buttons labeled 2D, Over, and Cam. Click the Over button.
- You will now have a 2 dimensional over view of your world. Look for evidence of your build. Move the mouse over this build. At the bottom of your screen, you will have coordinates.
Here is an image of the program with the Over button and the coordinates circled:
Click the image to enlarge. If you look close, my mouse is over what looks like gardens and trails. Evidence of a build or village and the coordinates are (-260, 0, 320).