Apple - Xcrun missing, installing Xcode Command Line Tools not fixing issue

Okay, After a full day of attempts, re-installing homebrew and all... found a solution which I should have tried a lot earlier in all honesty. Leaving it here if anyone else has the same problem in the future:

Doing xcode-select --install showed everything as being installed correctly but I just couldn't confirm that anywhere. I downloaded the CLT as a pkg from the apple developer website (https://developer.apple.com/download/more/) and installed it the old fashioned way. CLT is now installed and homebrew is detecting it just fine.

Brew Config now:

HOMEBREW_VERSION: 1.5.14
ORIGIN: https://github.com/Homebrew/brew
HEAD: 7fd6210127f088b6ee8708a1d7f4ec2df3fc5bb4
Last commit: 6 days ago
Core tap ORIGIN: https://github.com/Homebrew/homebrew-core
Core tap HEAD: 1f9ba958e21dce9673b932cfc1f55dd155f0df69
Core tap last commit: 31 hours ago
HOMEBREW_PREFIX: /usr/local
CPU: octa-core 64-bit haswell
Homebrew Ruby: 2.3.3 => /System/Library/Frameworks/Ruby.framework/Versions/2.3/usr/bin/ruby
Clang: 9.1 build 902
Git: 2.8.1 => /usr/local/bin/git
Curl: 7.54.0 => /usr/bin/curl
Java: 1.8.0_77
macOS: 10.13.3-x86_64
CLT: 9.3.0.0.1.1521514116
Xcode: N/A
XQuartz: N/A

Thanks Nimesh for helping me!

I had to check configuration of location as explained here to make it work:

You can just select command line tools from the XCode Preferences show in below screenshot.

You will be prompted for password.

If the above answer doesn't fully fix the problem you can also check Brew Doctor mine was also complaining that Xcode.app was in the wrong place and to fix suggested the fix.

sudo xcode-select -switch /Applications/Xcode.app

My /Applications folder had somehow changed from ~/ to /