How can I locate a stolen MacBook that didn't have Find My Mac turned on?
Without Find My Mac turned on via your iCloud account, you are going to have to rely on the kindness of strangers or local law enforcement to get it back.

Edit:

And my experience with a stolen computer was that even having Find My Mac enabled didn't help me get the computer back. The police would not use the location information to recover the computer. It is mostly for finding a lost computer or deleting your data so the thieves cannot gain access to your data.