I accidentaly forbid SSH connection to a remote server... What's next?

There are several alternatives:

• See if they have IPMI / "KVM" / console access to the server which lets you control it as if you had a physical keyboard plugged into it.
• If they don't offer that, see if you can boot the VM to a recovery linux CD (some providers offer this) and then correct the firewall rules that way and then boot it like normal.

• If you don't have console access, before you boot to recovery or attach the volume to another VM (as in the Amazon case, credit user3550767's answer), you can try Ankh2054's answer of rebooting first if you haven't saved the rules (likely the case since you kicked yourself out before you had a chance to save). Use the control panel or ask someone to power cycle it using a non-graceful reset / poweroff (aka hard reboot or hard shutdown) in case the init script saves the rules automatically when gracefully rebooting (credit @jfalcon, @joshudson).

  Weigh the drawbacks of this (such as data being written during reboot may be lost and filesystem check may be required on boot so longer boot up time, though that delay may be less than booting to recovery).

If you have not yet saved the IPtables rule, you can reboot server on VPS (if available) and the rule should disappear.

This is what human-staffed help lines are for. Call the service provider, and have one of their operators remove the rule for you.

A general way to fix a broken instance is to shut it down and attach the root volume to a working instance. You can then mount the volume there and view logs or edit configuration files. You can then detach the volume and start it up in its own instance.

Formal answer: go to VPS management panel, get local access (virtual KVM) somehow or call them.

Explanation of steps/rules to prevent falling for it again:

1. There are ip, routing and firewall rule changes that may go bad and block your access.
2. and it applies to dedicated network device configuration too, not to VPSes only

So unless you are 100% sure that you can recover.. I recommend to always make a way to reset network config to its previous state.. like, open background session with either screen, nohup, or tmux, even cron may work for this, and add iptables -F or other desired means to reset anything to the previous state.