自分の取った解決策はタイトル通りです。
自分一人で子供を連れて行くなら、男性が使えるオムツ替えスペースのある場所を選んで出掛けました。
大規模小売店にはほぼ確実にありますし、基本的に駅その他公共施設には多目的トイレがあるのでそれを使います。

1歳ならばとっくにパンツタイプのおむつだったし、つかまり立ちできたので、おむつ台は必要なし。

障がい者用トイレか男性用トイレの個室で、子供を立たせて交換していました。
もし男性禁止ならば、施設の係の方に一声かけて、中にだれもいないことを女性に確認してもらってから入るのがいいと思いますよ。授乳している方もいますから。通路など外ではおむつは交換しません。

首都圏在住一男の父ですが、その場合私ならば
・駅ビルのインフォメーションセンターに行き、自分が入れるおむつ替えスペースがあるか（多目的トイレなど)を聞く。あればそこで交換。
無ければ、
・駅に移動し同じ事を聞き、駅構内しか無ければ事情を話し中に入れてもらい交換。外にあれば、そこで交換。
それでも無ければ、
・駅周辺の別施設（デパートなど)おむつ替えスペースがあると思われる場所に移動して交換。
外でのおむつ替えは、高い台の上に子供を載せる場合がほとんどなので、
固定ベルトをしていても、自分が落ち着いて替えられる場所で無いと安心出来なません。（女性用トイレなんて私には入る勇気がありません。)
なので、直ぐに替えてあげたいのは山々ですが、そうしています。
トピ主さんは、比較的男性でもおむつ替え出来る場所を探せそうな所にお住まいのようですので、
まずは、自分の足でそういう場所を探しましょう。
また、同じ場面に遭遇した場合、あそこに確かあったという記憶は後々役に立ちますよ。

男性じゃなくてすみません
男性じゃなくても、世の中のお母さんはいろいろ工夫してると思いますよ。
今では大きい施設では大抵オムツ替えシートがありますが、小さい所はありませんよね。
車があれば、車内で。
なければ、お手洗いの洗面台の上(極狭スペース)とか、洋式便座の蓋を閉めて寝かせるなど、結構危険なことをせざるを得ない場合があります。

立てるようになると、新聞紙を１枚ずつ小さく畳んだものを用意しておくと便利ですよ。
子どもに靴を脱いでそこに立たせて、替えたらその新聞紙で包むと匂い漏れを防止できますし。

と言っても、まだまだ子育てしやすい環境は整ってませんね。
大変ですが、お互い頑張りましょうね。

多くの母親が出かける先に授乳室があるか、などをリサーチした上で赤ちゃん連れで出かけるように、オムツ替えが必要な乳幼児を連れて外出するならばオムツ替えのできる場所があるかリサーチしてから行きましょう。

やむを得ずでもお店の人とかに許可をもらっていない限り女性トイレはお勧めしません。

正式には「赤ちゃん休憩室」「赤ちゃんルーム」だと思いますが、モールなどの赤ちゃんルームならば、オムツ替えスペースぐらいなら男性も入室できる所は増えています。　ただ個室授乳室しかない所だと授乳するママさんを考慮してダメな所もあります。カーテンを開けてしまったりする人もいるので。

あと、多目的トイレがある所なら大体はオムツ替え台があるところが多いです。ちなみに男性でも替えられる台があるかは聞きましたか？一応聞く事で実はここにあったって勉強にもなりますよ。

１．絶対やめてください。　用途はオムツ替えでもマナー違反です。
２．これもやめた方が良いです。許可があるなら別ですが、通報される可能性あり
３．公共の場では基本オムツ替えはしない。自分の車の中ならOKだし、人気のない公園なら許容範囲。

当方　４０代男性
もう子供が小学生になりましたが、よくおむつ交換してました。基本的に障害者用トイレや授乳室で行いましたが・・・入出禁止は見たことがありません。
自分だったら、店員さんに場所を聞きますが、近くになければ、ベンチで行います。

私は女性なので申し訳ありませんが。
オムツ替え台がないところも多いですね。
ケータイショップで、遊ぶためのキッズスペースはとても充実してるのに
オムツ替え台はありませんでした。
一歳児ですが、いつも寝かせてオムツ替えるため、タイトルどおりにしました。
便器のふたにオムツがえシートひきました。やってやれないことはなかったです。
車で出かけてるときは車でやります。
カーディーラーも、キッズスペース充実でオムツ替え台なかったです。
うわべだけのサービスって感じですね。

赤ちゃん休憩室には、ほんとに狭くてオムツ替えベッドに授乳用のイスが並んでるだけのところもあります。
男性お断りとなっているからには、きちんと仕切られていないのでしょう。
そこに男性がいたらビックリします。女性トイレも。
お店の人に断って、ついていてもらうのでなければ、やめたほうがいいでしょう。
通路のベンチはなしでしょう。オムツはトイレと同等じゃないですか？

男性トイレにもオムツ替え台、増えると良いですね。
公共施設（市役所、図書館など）はあるところ多いですね。

障害者用トイレ

男女誰でも入れて、スペースが広い。ベビーカーごと入れます。