Update for Gerrit 3+ (using NoteDB):
When submitting a change (or even just pushing it, apparently) Gerrit creates a new patchset to a change, which comes with a "merged" attribute. This needs to be undone.
For a changeset 12345, you'll need to check out the git history of refs/changes/45/12345/meta. That "branch" contains the discussion to the changeset.
By resetting that branch to the last commit before the submission (the submission should have a message like "Create patch set 2", with an attribute "Status: merged" - take its parent) you remove all knowledge that the change has ever been merged.
You might have to flush the caches, too - I just did "gerrit flush-caches --all" on the SSH interface to be sure.