Authenticating a user via SMS

It sounds like what you're looking for is an "out of band" code or token. This means you want something that's not accessible to someone who physically has the phone. So things like emails and Google Authenticator are out.

I'm assuming that users will do (at least) first-time account setup through a web-browser, what about having them enter an "SMS PIN" which the chatbot will later prompt them for?

This is similar to using the last 4 digits of their credit card number in that it will be in their SMS history and a phone thief can make charges to your chat bot. What makes me nervous about CC digits is that for convenience of your service, you are increasing your users' risk of identity theft.

As you pointed out in your question: if the user gets their phone stolen and the attacker gets past the lock screen, they're kinda sunk anyway. What you are really protecting against is somebody impersonating your user from a different phone through SMS spoofing the from: number. In this regard either an email one-time password, or a pre-set pin will give you the security you need.

Would a small mobile app be out of the question?

It would handle all incoming and outgoing messages (for the relevant messages of course) it would delete all sent and received messages (from the app). It would require a pin number to access which the user would have to enter each time. Maybe some basic encryption of the message as well?

As an additional benefit it would increase usability in that it could create the SMS using prompts rather then having to remember the right abbreviations and formatting of messages.