Dunno if you're performing alone or in a group, but you might get some ideas from my midi sequence...

http://members.shaw.ca/tunebook/chevaliers.htm

If you have sequencing software you'll be able to pick out the harmony track and the 'wandering' base line. The key change helps, too, in a song like this where there are many verses.