So I want to try out modding for Deus Ex but have no idea where to find the SDK, the one I found is asking for 1109f version, while I have GOTY from GOG, Does anyone know where can I find the SDK and will it work with GOG version?

In the following link you can find v1112. Hope it works for you!

http://www.moddb.com/games/deus-ex/downloads/sdk-v1112fm

Also there is on this link too along with v1109f:

http://www.unrealtexture.com/Unreal/Website/Downloads/UEBG/DeusEx/Editor/Editor.htm

It's showing me an error that I don't have Deus Ex installed even though I do

Where do you have Deus Ex installed? I mean in which directory (eg Program Files). If you have it installed in the Program Files folder, maybe if you uninstall the game and install it again in a different directory (eg "C:\Games\Deus Ex" or "C:\Deus Ex") fixes the problem.

Try this and report back!

ps. Another trick you can try, is to extract the SDK executable you have (with WinRAR or whatever else you use) in the Deus Ex directory. Then you'll need to install the ConEdit.exe. But before doing this, make a new install as i wrote above.

The GOG version should be 1.112fm and that's the version the SDK was released for, so either you've got an older version, e.g. by using a custom launcher or you're using an outdated version of the SDK.
Try the official SDK from here and make sure you're working on a vanilla installation of GOG's version.

Had Fresh Install, same problem, so I just downloaded Deus Ex Editing Pack from Offtopic productions and installed that.
Here's the link if anyone is intrested
http://www.offtopicproductions.com/forum/viewtopic.php?f=36&t=10464