I want to change DPI with ImageMagick without changing the actual byte-size of the image data

Specify the units - I seem to remember having a problem when I omitted this option (although DPI should be the default), for example:

convert -units PixelsPerInch input.png -density 300 output.png

Do you know which embedded data fields GIMP uses to read the resolution - does it have its own that override the standard ones used by ImageMagick? For example, Photoshop uses Photoshop:XResolution and Photoshop:YResolution so you have to set these for Photoshop to recognise a density setting (ImageMagick can’t do this - we use ExifTool).

Note that you can use Exiftool to read out resolutions. For example, Exiftool '-*resolution*' c.jpg might show

Resolution Unit : inches X Resolution : 300 Y Resolution : 300

Exiftool also is able to set parameters, but as noted in man page Image::ExifTool::TagNames, the Extra Tags XResolution and YResolution are not writable by Exiftool.

I don't know whether ImageMagick has resolution-changing options, but would be surprised if it doesn't. Also, it is straightforward to write GIMP scripts to automate tasks like this, and also it is possible to change resolutions with small programs. For example, following is a C program (compilable via gcc setRes.c -O3 -Wall -o setRes) that reads the first few bytes of a jpeg file, changes resolutions to 300, and rewrites them. The program as shown uses constants for little-endian machines, like x86. If run on a big-endian machine it should terminate with a message like Error: xyz may be not a .jpg file, even if xyz is a jpeg file. Note, I haven't tested the resulting pictures via pdflatex; you probably would find it worthwhile to post a question in the tex SE.

/* jiw -- 24 Sep 2012 -- Re: set resolution in a jpg -- Offered without
warranty under GPL v3 terms as at http://www.gnu.org/licenses/gpl.html
*/
#include <stdlib.h>
#include <stdio.h>
void errorExit(char *msg, char *par, int fe) {
  fprintf (stderr, "\n%3d Error: %s %s\n", fe, msg, par);
  exit (1);
}
// Note, hex constants are byte-reversed on little vs big endian machines
enum { JF=0x464a, IF=0x4649, L300=0x2c01, B300=0x012c, NEWRES=L300};
int main(int argc, char *argv[]) {
  FILE *fi;
  short int buf[9];
  int r, L=sizeof buf;
  if (argc<2) errorExit(argv[0], "requires a .jpg file name", 0);
  fi = fopen(argv[1], "r+b");
  if(!fi) errorExit("open failed for", argv[1], ferror(fi));
  r = fread(buf, 1, L, fi);
  if (r != L) errorExit("read failed for", argv[1], ferror(fi));
  if (buf[3] != JF || buf[4] != IF) // Check JFIF signature
    errorExit(argv[1], "may be not a .jpg file", 0);
  buf[7] = buf[8] = NEWRES;
  fseek(fi, 0, SEEK_SET);
  r = fwrite(buf, 1, L, fi);
  if (r != L) errorExit("write failed for", argv[1], ferror(fi));
  return 0;
}

I could not figure out how to convince convert to only add the metadata and not re-encode my [monochrome] bitmap; it was expanding the file >50%.

I discovered that pngcrush (not an ImageMagick tool) can also add the density metadata. This command line marks it 600dpi and allows other optimizations, which reduced the file size by ~10%:

pngcrush -res 600 in.png out.png