I go with KaTrian, let him speak with bad grammar. Let's say, for example, that he is from a Slavic country. There are no articles in most Slavic languages so he also won't use any when speaking English.
That's a good example, articles. Also, simple vocabulary. Perhaps he fumbles for some specific word a couple of times. You can also add authenticity with him translating idioms from his mothertongue -- they never seem to work as translations and would add foreign flavor. Accent-wise, it might be sufficient if you just mention it through the characters. Perhaps there's a foreign cadence to his speech, perhaps his 'r's are too rhotic or he doesn't distinguish between voiced and unvoiced consonants. You can throw a few things in. If he's French, you could probably spell a few plurals without the -s because Francophones don't pronounce it in French. Or words that end in -tion, like 'attention,' there're differences how e.g. Swedes, French, and Finns might mispronounce it by accident. When you communicate in several languages, things get mixed up even when you know how to pronounce something. As far as dialect goes. I can see two things happening: 1) he's learned some local English dialect and uses words that aren't used in the region where your story takes place. 2) He isn't really able to distinguish between dialects (or registers!), so he mixes and matches, using some word he learned when he was, say, in Newcastle, UK, another that he learned in Dublin, something else he picked up in NYC, etc. If you really want to eff with the reader, give your character a first language with personal pronouns that don't distinguish between genders.
I agree that bad grammar is a good idea, much better than spelling out your character's words phonetically. One thing you could try in addition to that is have the character speak in a more formal manner, like he is reading from a textbook. For example, when I first met my fiance, he was already pretty fluent in English but one thing I noticed quickly is that he never used contractions. It was always "can not" or "we will" or "it is," never "can't" or "we'll" or "it's." He has grown out of it now that he is more comfortable with the language, after speaking it almost every day for the last six years, but he still mixes up both articles and pronouns on occasion. Also, the KaTrian's idea about the idioms is a great way to add some very authentic humor. I about died laughing the first time he told me "When one donkey speaks, the other lowers his ears." or when his mom called me a "good fork" the first time I ate dinner with his parents.
I am totally on board with grammar being off, and maybe a few instances of mispronounced/"misspelled" words being introduced. I, personally, can't stand heavy accents being phonetically spelled... I've encountered it once in a book and that was more than I wanted. A friend recommended The Tower of Ravens: Book One of Rhiannon's Ride by Kate Forsyth. One of (or just) the main characters had a super thick phonetic accent AND used regional dialect. I didn't understand most of what she said and constantly got headaches from trying to figure it out. I ended up setting the book down and haven't yet had the courage to pick it up again. On the other hand, I read a short story by... curses. I don't think it was Amy Tan, but she does it too. Anyway, it's English as a second language per Chinese immigrants. I believe the grammar is all that was askew there. I've slept too many times since I read these... From what I remember, I could hear the accent perfectly due to the grammar and word choice. There were no phonetic "aids" necessary. I'll see if I can find the story I had in mind when I get home... EDIT: A little late, but the story I was thinking of was Gish Jen's "Who's Irish?" It was published in 1999, so it may require some effort to acquire it if you care to check it out.
Terry pratchett doed it. And I love the disc world novels byt sometimes the accents leave me confused and re reading. I agree with Cog. Very small times if at all. Emphasis when needed.
I think you can use sentence structure to convey an accent, more than spelling out how the words would sound... Have you read The Goldfinch by Donna Tartt? She conveys Russian accents in an extraordinary way - you can hear them speaking in your head even though she's using normal English words, just by the way the sentences are structured. Take a look - it's an extraordinary read anyway... [link removed]