If you hadn't already looked, try the south east corner at 351, 347. You should a camp fire going with a chest sitting nearby against what looks like some ruins. If you dig through the earth in a counter-clockwise route along those ruins, you'll uncover a large(and I mean LARGE) spiral staircase leading downward with several strange structures built down there. One area will have Netherrack along its surfaces. There should be a portal to the Nether sitting within this area.