I've defeated all trainers in my way, all trainers out of my way as well :P
I'm currently at Mosdeep city, and my Pokemon are around level 37. Where can I train which will level me up to 40 fast?
The Seafloor Cavern is the place you want to be. Featuring wild Pokemon +35 and a number of Team Magma Grunts, this is the place you want to visit. Just travel south from Mossdeep City and head underwater, you will reach an excellent levelling ground as well as the next step in your quest to reach Sootpolis and the 8th gym.