Fireballs will work, but you'll need lots.
From experience, you're best off doing this if he starts in a bad place. In one Amurite game, he started next to the Bannor, so I got an open borders agreement, hid in Bannorland (or whatever their nation is called), and chunked fireballs from there. Mister Big Bad Demon was too much of a wuss to break a treaty, so I basically killed his entire nation with fire.