I have a good tip for finding strongholds.
1. It must be at least or around (a little over) 1000 blocks away from X:0
2. It must be at least or around (a little over) 1000 blocks away from Z:0
3. Once you get to X:1000 Y:# Z:1000, throw one ender eye. If it goes forward, go in its direction about 100 blocks, then throw another one. Repeat this process until it starts going downwards.
4. Once you see it go downwards, go towards the direction where it's sloping down, and throw an eye once you reach about 30 blocks in that direction.
5. Once it goes straight down, move over a few blocks, and dig down.
6. Boom. End Portal (most likely).