Firebase rate limiting in security rules?

The trick is to keep an audit of the last time a user posted a message. Then you can enforce the time each message is posted based on the audit value:

{
  "rules": {
          // this stores the last message I sent so I can throttle them by timestamp
      "last_message": {
        "$user": {
          // timestamp can't be deleted or I could just recreate it to bypass our throttle
          ".write": "newData.exists() && auth.uid === $user",
          // the new value must be at least 5000 milliseconds after the last (no more than one message every five seconds)
          // the new value must be before now (it will be since `now` is when it reaches the server unless I try to cheat)
          ".validate": "newData.isNumber() && newData.val() === now && (!data.exists() || newData.val() > data.val()+5000)"
        }
      },

      "messages": {
        "$message_id": {
          // message must have a timestamp attribute and a sender attribute
          ".write": "newData.hasChildren(['timestamp', 'sender', 'message'])",
          "sender": {
            ".validate": "newData.val() === auth.uid"
          },
          "timestamp": {
            // in order to write a message, I must first make an entry in timestamp_index
            // additionally, that message must be within 500ms of now, which means I can't
            // just re-use the same one over and over, thus, we've effectively required messages
            // to be 5 seconds apart
            ".validate": "newData.val() >= now - 500 && newData.val() === data.parent().parent().parent().child('last_message/'+auth.uid).val()"
          },
          "message": {
            ".validate": "newData.isString() && newData.val().length < 500" 
          },
          "$other": {
            ".validate": false 
          }
        }
      } 
  }
}

See it in action in this fiddle. Here's the gist of what's in the fiddle:

var fb = new Firebase(URL);
var userId; // log in and store user.uid here

// run our create routine
createRecord(data, function (recordId, timestamp) {
   console.log('created record ' + recordId + ' at time ' + new Date(timestamp));
});

// updates the last_message/ path and returns the current timestamp
function getTimestamp(next) {
    var ref = fb.child('last_message/' + userId);
    ref.set(Firebase.ServerValue.TIMESTAMP, function (err) {
        if (err) { console.error(err); }
        else {
            ref.once('value', function (snap) {
                next(snap.val());
            });
        }
    });
}

function createRecord(data, next) {
    getTimestamp(function (timestamp) {
        // add the new timestamp to the record data
        var data = {
          sender: userId,
          timestamp: timestamp,
          message: 'hello world'
        };

        var ref = fb.child('messages').push(data, function (err) {
            if (err) { console.error(err); }
            else {
               next(ref.name(), timestamp);
            }
        });
    })
}

I don't have enough reputations to write in the comment, but I agree to Victor's comment. If you insert the fb.child('messages').push(...) into a loop (i.e. for (let i = 0; i < 100; i++) {...} ) then it would successfully push 60-80 meessages ( in that 500ms window frame.

Inspired by Kato's solution, I propose a modification to the rules as follow:

rules: {
  users: {
    "$uid": {
      "timestamp": { // similar to Kato's answer
        ".write": "auth.uid === $uid && newData.exists()"
        ,".read": "auth.uid === $uid"
        ,".validate": "newData.hasChildren(['time', 'key'])"
        ,"time": {
          ".validate": "newData.isNumber() && newData.val() === now && (!data.exists() || newData.val() > data.val() + 1000)"
        }
        ,"key": {

        }
      }
      ,"messages": {
        "$key": { /// this key has to be the same is the key in timestamp (checked by .validate)
           ".write": "auth.uid === $uid && !data.exists()" ///only 'create' allow
           ,".validate": "newData.hasChildren(['message']) && $key === root.child('/users/' + $uid + '/timestamp/key').val()"
           ,"message": { ".validate": "newData.isString()" }
           /// ...and any other datas such as 'time', 'to'....
        }
      }
    }
  }
}

The .js code is quite similar to Kato's solution, except that the getTimestamp would return {time: number, key: string} to the next callback. Then we would just have to ref.update({[key]: data})

This solution avoids the 500ms time-window, we don't have to worry that the client must be fast enough to push the message within 500ms. If multiple write requests are sent (spamming), they can only write into 1 single key in the messages. Optionally, the create-only rule in messages prevents that from happening.