Is there is a way to send a local message from a Mac to an iOS device *without* the Internet? I know I can send Prowl notifications from OS X to iOS, but that requires going over the Internet.

I'd like to accomplish the same thing, except that I want to be able to be able to do it without an Internet connection, to be able to send a message from a Mac to (an) iOS device(s) on the same LAN/Wi-Fi network. 

(It doesn't have to be with Prowl, it could be with any iOS app, as long as it can receive a message from OS X.)
If I understand you correctly you're asking how to push local notifications on your Mac to your iOS device (hence using Prowl as an example)? Well since Mavericks/iOS 7 if both your Mac and iOS device support Bluetooth Low Energy, you could use a service based on the Apple Notification  Center Service.
This feature is also covered in this 9to5mac article.