Yes, it can be recovered.
As long as shutter does not use layer (it almost certainly does not) and as long as the black is really all black (it must not be transparent), it is enough.
The picture that you provided uses some amount of transparency, see here:
All I had to do is use the Fill tool in MS Paint. If I used some algorithm that would take the jpg compression into account, I could probably get better results.
Solution:
Use an editor that does not make the block transparent. Make sure layers are not used. Make sure change history is not stored (to allow undo) in the file. I believe MS paint + bitmap format satisfy all the requirements. Most editors combined with bitmap (BMP) format without compression should satisfy these requirements, but I can not confirm this.
Remove the data. You can do so in many editors by selecting it and pressing delete or Ctrl + X. Then apply redaction graphics, whether black box, or anything else.
DO NOT use JPEG (jpg) or other lossy formats anywhere from capture until redaction. JPEG may leave artifacts that may convey information about the deleted pixels. This may also apply to other lossy formats, use lossless formats if possible. Using any format after the image is redacted is fine.
As lossless formats may also retain some information, if they are not completely re-encoded after the edit, it is recommended to either only use pure bitmap format with no compression before redacting, or to change the format after redacting.
Double check:
You can double check no compression is used in BMP format by checking the file size. The size should be larger than color_depth / 8 * width * height
(resolution in pixels, color depth usually 24). Note that this check will not reveal transparency and artifacts caused by lossy compression, so make extra sure you did not use lossy format at any point.
It may also be useful to post a specific question about your proposed setup here, so you can see additional opinions and recommendations. It is hard to give definitive answer, that would work in general for all platforms, formats and editors as they all have their specific caveats.